home *** CD-ROM | disk | FTP | other *** search
| MacBinary | 1993-11-08 | 31.6 KB | [TEXT/KAHL] |
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: MacBinary
(archive/macBinary).
You can browse this item here: inflate.c
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 66%
| dexvert
| Compact Compressed (Unix) (archive/compact)
| ext
| Supported |
| 10%
| dexvert
| MacBinary (archive/macBinary)
| fallback
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| MacBinary II, Mon Nov 8 10:40:03 1993, modified Mon Nov 8 10:40:03 1993, creator Think C, type ASCII, 31730 bytes "inflate.c" , at 0x7c72 400 bytes resource
| default (weak)
| |
| 99%
| file
| data
| default
| |
| 74%
| TrID
| Macintosh plain text (MacBinary)
| default
| |
| 25%
| TrID
| MacBinary 2
| default (weak)
| |
| 100%
| siegfried
| fmt/1762 MacBinary (II)
| default
| |
| 100%
| lsar
| MacBinary
| default
|
|
| id metadata |
|---|
| key | value |
|---|
| macFileType | [TEXT] |
| macFileCreator | [KAHL] |
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 09 69 6e 66 6c 61 74 | 65 2e 63 00 00 00 00 00 |..inflat|e.c.....|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 4b 41 48 | 4c 00 00 00 00 00 00 00 |.TEXTKAH|L.......|
|00000050| 00 00 00 00 00 7b f2 00 | 00 01 90 a9 04 18 d3 a9 |.....{..|........|
|00000060| 04 18 d3 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 f9 1f 00 00 |........|........|
|00000080| 2f 2a 20 69 6e 66 6c 61 | 74 65 2e 63 20 2d 2d 20 |/* infla|te.c -- |
|00000090| 4e 6f 74 20 63 6f 70 79 | 72 69 67 68 74 65 64 20 |Not copy|righted |
|000000a0| 31 39 39 32 20 62 79 20 | 4d 61 72 6b 20 41 64 6c |1992 by |Mark Adl|
|000000b0| 65 72 0d 20 20 20 76 65 | 72 73 69 6f 6e 20 63 31 |er. ve|rsion c1|
|000000c0| 30 70 31 2c 20 31 30 20 | 4a 61 6e 75 61 72 79 20 |0p1, 10 |January |
|000000d0| 31 39 39 33 20 2a 2f 0d | 0d 2f 2a 20 59 6f 75 20 |1993 */.|./* You |
|000000e0| 63 61 6e 20 64 6f 20 77 | 68 61 74 65 76 65 72 20 |can do w|hatever |
|000000f0| 79 6f 75 20 6c 69 6b 65 | 20 77 69 74 68 20 74 68 |you like| with th|
|00000100| 69 73 20 73 6f 75 72 63 | 65 20 66 69 6c 65 2c 20 |is sourc|e file, |
|00000110| 74 68 6f 75 67 68 20 49 | 20 77 6f 75 6c 64 0d 20 |though I| would. |
|00000120| 20 20 70 72 65 66 65 72 | 20 74 68 61 74 20 69 66 | prefer| that if|
|00000130| 20 79 6f 75 20 6d 6f 64 | 69 66 79 20 69 74 20 61 | you mod|ify it a|
|00000140| 6e 64 20 72 65 64 69 73 | 74 72 69 62 75 74 65 20 |nd redis|tribute |
|00000150| 69 74 20 74 68 61 74 20 | 79 6f 75 20 69 6e 63 6c |it that |you incl|
|00000160| 75 64 65 0d 20 20 20 63 | 6f 6d 6d 65 6e 74 73 20 |ude. c|omments |
|00000170| 74 6f 20 74 68 61 74 20 | 65 66 66 65 63 74 20 77 |to that |effect w|
|00000180| 69 74 68 20 79 6f 75 72 | 20 6e 61 6d 65 20 61 6e |ith your| name an|
|00000190| 64 20 74 68 65 20 64 61 | 74 65 2e 20 20 54 68 61 |d the da|te. Tha|
|000001a0| 6e 6b 20 79 6f 75 2e 0d | 20 20 20 5b 54 68 65 20 |nk you..| [The |
|000001b0| 68 69 73 74 6f 72 79 20 | 68 61 73 20 62 65 65 6e |history |has been|
|000001c0| 20 6d 6f 76 65 64 20 74 | 6f 20 74 68 65 20 66 69 | moved t|o the fi|
|000001d0| 6c 65 20 43 68 61 6e 67 | 65 4c 6f 67 2e 5d 0d 20 |le Chang|eLog.]. |
|000001e0| 2a 2f 0d 20 0d 2f 2a 0d | 20 2a 20 4d 6f 64 69 66 |*/. ./*.| * Modif|
|000001f0| 69 65 64 3a 31 39 39 33 | 20 62 79 20 53 50 44 73 |ied:1993| by SPDs|
|00000200| 6f 66 74 20 66 6f 72 20 | 4d 61 63 47 7a 69 70 0d |oft for |MacGzip.|
|00000210| 20 2a 0d 20 2a 2f 0d 0d | 0d 2f 2a 0d 20 20 20 49 | *. */..|./*. I|
|00000220| 6e 66 6c 61 74 65 20 64 | 65 66 6c 61 74 65 64 20 |nflate d|eflated |
|00000230| 28 50 4b 5a 49 50 27 73 | 20 6d 65 74 68 6f 64 20 |(PKZIP's| method |
|00000240| 38 20 63 6f 6d 70 72 65 | 73 73 65 64 29 20 64 61 |8 compre|ssed) da|
|00000250| 74 61 2e 20 20 54 68 65 | 20 63 6f 6d 70 72 65 73 |ta. The| compres|
|00000260| 73 69 6f 6e 0d 20 20 20 | 6d 65 74 68 6f 64 20 73 |sion. |method s|
|00000270| 65 61 72 63 68 65 73 20 | 66 6f 72 20 61 73 20 6d |earches |for as m|
|00000280| 75 63 68 20 6f 66 20 74 | 68 65 20 63 75 72 72 65 |uch of t|he curre|
|00000290| 6e 74 20 73 74 72 69 6e | 67 20 6f 66 20 62 79 74 |nt strin|g of byt|
|000002a0| 65 73 20 28 75 70 20 74 | 6f 20 61 0d 20 20 20 6c |es (up t|o a. l|
|000002b0| 65 6e 67 74 68 20 6f 66 | 20 32 35 38 29 20 69 6e |ength of| 258) in|
|000002c0| 20 74 68 65 20 70 72 65 | 76 69 6f 75 73 20 33 32 | the pre|vious 32|
|000002d0| 4b 20 62 79 74 65 73 2e | 20 20 49 66 20 69 74 20 |K bytes.| If it |
|000002e0| 64 6f 65 73 6e 27 74 20 | 66 69 6e 64 20 61 6e 79 |doesn't |find any|
|000002f0| 0d 20 20 20 6d 61 74 63 | 68 65 73 20 28 6f 66 20 |. matc|hes (of |
|00000300| 61 74 20 6c 65 61 73 74 | 20 6c 65 6e 67 74 68 20 |at least| length |
|00000310| 33 29 2c 20 69 74 20 63 | 6f 64 65 73 20 74 68 65 |3), it c|odes the|
|00000320| 20 6e 65 78 74 20 62 79 | 74 65 2e 20 20 4f 74 68 | next by|te. Oth|
|00000330| 65 72 77 69 73 65 2c 20 | 69 74 0d 20 20 20 63 6f |erwise, |it. co|
|00000340| 64 65 73 20 74 68 65 20 | 6c 65 6e 67 74 68 20 6f |des the |length o|
|00000350| 66 20 74 68 65 20 6d 61 | 74 63 68 65 64 20 73 74 |f the ma|tched st|
|00000360| 72 69 6e 67 20 61 6e 64 | 20 69 74 73 20 64 69 73 |ring and| its dis|
|00000370| 74 61 6e 63 65 20 62 61 | 63 6b 77 61 72 64 73 20 |tance ba|ckwards |
|00000380| 66 72 6f 6d 0d 20 20 20 | 74 68 65 20 63 75 72 72 |from. |the curr|
|00000390| 65 6e 74 20 70 6f 73 69 | 74 69 6f 6e 2e 20 20 54 |ent posi|tion. T|
|000003a0| 68 65 72 65 20 69 73 20 | 61 20 73 69 6e 67 6c 65 |here is |a single|
|000003b0| 20 48 75 66 66 6d 61 6e | 20 63 6f 64 65 20 74 68 | Huffman| code th|
|000003c0| 61 74 20 63 6f 64 65 73 | 20 62 6f 74 68 0d 20 20 |at codes| both. |
|000003d0| 20 73 69 6e 67 6c 65 20 | 62 79 74 65 73 20 28 63 | single |bytes (c|
|000003e0| 61 6c 6c 65 64 20 22 6c | 69 74 65 72 61 6c 73 22 |alled "l|iterals"|
|000003f0| 29 20 61 6e 64 20 6d 61 | 74 63 68 20 6c 65 6e 67 |) and ma|tch leng|
|00000400| 74 68 73 2e 20 20 41 20 | 73 65 63 6f 6e 64 20 48 |ths. A |second H|
|00000410| 75 66 66 6d 61 6e 0d 20 | 20 20 63 6f 64 65 20 63 |uffman. | code c|
|00000420| 6f 64 65 73 20 74 68 65 | 20 64 69 73 74 61 6e 63 |odes the| distanc|
|00000430| 65 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 2c 20 77 |e inform|ation, w|
|00000440| 68 69 63 68 20 66 6f 6c | 6c 6f 77 73 20 61 20 6c |hich fol|lows a l|
|00000450| 65 6e 67 74 68 20 63 6f | 64 65 2e 20 20 45 61 63 |ength co|de. Eac|
|00000460| 68 0d 20 20 20 6c 65 6e | 67 74 68 20 6f 72 20 64 |h. len|gth or d|
|00000470| 69 73 74 61 6e 63 65 20 | 63 6f 64 65 20 61 63 74 |istance |code act|
|00000480| 75 61 6c 6c 79 20 72 65 | 70 72 65 73 65 6e 74 73 |ually re|presents|
|00000490| 20 61 20 62 61 73 65 20 | 76 61 6c 75 65 20 61 6e | a base |value an|
|000004a0| 64 20 61 20 6e 75 6d 62 | 65 72 0d 20 20 20 6f 66 |d a numb|er. of|
|000004b0| 20 22 65 78 74 72 61 22 | 20 28 73 6f 6d 65 74 69 | "extra"| (someti|
|000004c0| 6d 65 73 20 7a 65 72 6f | 29 20 62 69 74 73 20 74 |mes zero|) bits t|
|000004d0| 6f 20 67 65 74 20 74 6f | 20 61 64 64 20 74 6f 20 |o get to| add to |
|000004e0| 74 68 65 20 62 61 73 65 | 20 76 61 6c 75 65 2e 20 |the base| value. |
|000004f0| 20 41 74 0d 20 20 20 74 | 68 65 20 65 6e 64 20 6f | At. t|he end o|
|00000500| 66 20 65 61 63 68 20 64 | 65 66 6c 61 74 65 64 20 |f each d|eflated |
|00000510| 62 6c 6f 63 6b 20 69 73 | 20 61 20 73 70 65 63 69 |block is| a speci|
|00000520| 61 6c 20 65 6e 64 2d 6f | 66 2d 62 6c 6f 63 6b 20 |al end-o|f-block |
|00000530| 28 45 4f 42 29 20 6c 69 | 74 65 72 61 6c 2f 0d 20 |(EOB) li|teral/. |
|00000540| 20 20 6c 65 6e 67 74 68 | 20 63 6f 64 65 2e 20 20 | length| code. |
|00000550| 54 68 65 20 64 65 63 6f | 64 69 6e 67 20 70 72 6f |The deco|ding pro|
|00000560| 63 65 73 73 20 69 73 20 | 62 61 73 69 63 61 6c 6c |cess is |basicall|
|00000570| 79 3a 20 67 65 74 20 61 | 20 6c 69 74 65 72 61 6c |y: get a| literal|
|00000580| 2f 6c 65 6e 67 74 68 0d | 20 20 20 63 6f 64 65 3b |/length.| code;|
|00000590| 20 69 66 20 45 4f 42 20 | 74 68 65 6e 20 64 6f 6e | if EOB |then don|
|000005a0| 65 3b 20 69 66 20 61 20 | 6c 69 74 65 72 61 6c 2c |e; if a |literal,|
|000005b0| 20 65 6d 69 74 20 74 68 | 65 20 64 65 63 6f 64 65 | emit th|e decode|
|000005c0| 64 20 62 79 74 65 3b 20 | 69 66 20 61 0d 20 20 20 |d byte; |if a. |
|000005d0| 6c 65 6e 67 74 68 20 74 | 68 65 6e 20 67 65 74 20 |length t|hen get |
|000005e0| 74 68 65 20 64 69 73 74 | 61 6e 63 65 20 61 6e 64 |the dist|ance and|
|000005f0| 20 65 6d 69 74 20 74 68 | 65 20 72 65 66 65 72 72 | emit th|e referr|
|00000600| 65 64 2d 74 6f 20 62 79 | 74 65 73 20 66 72 6f 6d |ed-to by|tes from|
|00000610| 20 74 68 65 0d 20 20 20 | 73 6c 69 64 69 6e 67 20 | the. |sliding |
|00000620| 77 69 6e 64 6f 77 20 6f | 66 20 70 72 65 76 69 6f |window o|f previo|
|00000630| 75 73 6c 79 20 65 6d 69 | 74 74 65 64 20 64 61 74 |usly emi|tted dat|
|00000640| 61 2e 0d 0d 20 20 20 54 | 68 65 72 65 20 61 72 65 |a... T|here are|
|00000650| 20 28 63 75 72 72 65 6e | 74 6c 79 29 20 74 68 72 | (curren|tly) thr|
|00000660| 65 65 20 6b 69 6e 64 73 | 20 6f 66 20 69 6e 66 6c |ee kinds| of infl|
|00000670| 61 74 65 20 62 6c 6f 63 | 6b 73 3a 20 73 74 6f 72 |ate bloc|ks: stor|
|00000680| 65 64 2c 20 66 69 78 65 | 64 2c 20 61 6e 64 0d 20 |ed, fixe|d, and. |
|00000690| 20 20 64 79 6e 61 6d 69 | 63 2e 20 20 54 68 65 20 | dynami|c. The |
|000006a0| 63 6f 6d 70 72 65 73 73 | 6f 72 20 64 65 61 6c 73 |compress|or deals|
|000006b0| 20 77 69 74 68 20 73 6f | 6d 65 20 63 68 75 6e 6b | with so|me chunk|
|000006c0| 20 6f 66 20 64 61 74 61 | 20 61 74 20 61 20 74 69 | of data| at a ti|
|000006d0| 6d 65 2c 20 61 6e 64 0d | 20 20 20 64 65 63 69 64 |me, and.| decid|
|000006e0| 65 73 20 77 68 69 63 68 | 20 6d 65 74 68 6f 64 20 |es which| method |
|000006f0| 74 6f 20 75 73 65 20 6f | 6e 20 61 20 63 68 75 6e |to use o|n a chun|
|00000700| 6b 2d 62 79 2d 63 68 75 | 6e 6b 20 62 61 73 69 73 |k-by-chu|nk basis|
|00000710| 2e 20 20 41 20 63 68 75 | 6e 6b 20 6d 69 67 68 74 |. A chu|nk might|
|00000720| 0d 20 20 20 74 79 70 69 | 63 61 6c 6c 79 20 62 65 |. typi|cally be|
|00000730| 20 33 32 4b 20 6f 72 20 | 36 34 4b 2e 20 20 49 66 | 32K or |64K. If|
|00000740| 20 74 68 65 20 63 68 75 | 6e 6b 20 69 73 20 75 6e | the chu|nk is un|
|00000750| 63 6f 6d 70 72 65 73 73 | 69 62 6c 65 2c 20 74 68 |compress|ible, th|
|00000760| 65 6e 20 74 68 65 0d 20 | 20 20 22 73 74 6f 72 65 |en the. | "store|
|00000770| 64 22 20 6d 65 74 68 6f | 64 20 69 73 20 75 73 65 |d" metho|d is use|
|00000780| 64 2e 20 20 49 6e 20 74 | 68 69 73 20 63 61 73 65 |d. In t|his case|
|00000790| 2c 20 74 68 65 20 62 79 | 74 65 73 20 61 72 65 20 |, the by|tes are |
|000007a0| 73 69 6d 70 6c 79 20 73 | 74 6f 72 65 64 20 61 73 |simply s|tored as|
|000007b0| 0d 20 20 20 69 73 2c 20 | 65 69 67 68 74 20 62 69 |. is, |eight bi|
|000007c0| 74 73 20 70 65 72 20 62 | 79 74 65 2c 20 77 69 74 |ts per b|yte, wit|
|000007d0| 68 20 6e 6f 6e 65 20 6f | 66 20 74 68 65 20 61 62 |h none o|f the ab|
|000007e0| 6f 76 65 20 63 6f 64 69 | 6e 67 2e 20 20 54 68 65 |ove codi|ng. The|
|000007f0| 20 62 79 74 65 73 20 61 | 72 65 0d 20 20 20 70 72 | bytes a|re. pr|
|00000800| 65 63 65 64 65 64 20 62 | 79 20 61 20 63 6f 75 6e |eceded b|y a coun|
|00000810| 74 2c 20 73 69 6e 63 65 | 20 74 68 65 72 65 20 69 |t, since| there i|
|00000820| 73 20 6e 6f 20 6c 6f 6e | 67 65 72 20 61 6e 20 45 |s no lon|ger an E|
|00000830| 4f 42 20 63 6f 64 65 2e | 0d 0d 20 20 20 49 66 20 |OB code.|.. If |
|00000840| 74 68 65 20 64 61 74 61 | 20 69 73 20 63 6f 6d 70 |the data| is comp|
|00000850| 72 65 73 73 69 62 6c 65 | 2c 20 74 68 65 6e 20 65 |ressible|, then e|
|00000860| 69 74 68 65 72 20 74 68 | 65 20 66 69 78 65 64 20 |ither th|e fixed |
|00000870| 6f 72 20 64 79 6e 61 6d | 69 63 20 6d 65 74 68 6f |or dynam|ic metho|
|00000880| 64 73 0d 20 20 20 61 72 | 65 20 75 73 65 64 2e 20 |ds. ar|e used. |
|00000890| 20 49 6e 20 74 68 65 20 | 64 79 6e 61 6d 69 63 20 | In the |dynamic |
|000008a0| 6d 65 74 68 6f 64 2c 20 | 74 68 65 20 63 6f 6d 70 |method, |the comp|
|000008b0| 72 65 73 73 65 64 20 64 | 61 74 61 20 69 73 20 70 |ressed d|ata is p|
|000008c0| 72 65 63 65 64 65 64 20 | 62 79 0d 20 20 20 61 6e |receded |by. an|
|000008d0| 20 65 6e 63 6f 64 69 6e | 67 20 6f 66 20 74 68 65 | encodin|g of the|
|000008e0| 20 6c 69 74 65 72 61 6c | 2f 6c 65 6e 67 74 68 20 | literal|/length |
|000008f0| 61 6e 64 20 64 69 73 74 | 61 6e 63 65 20 48 75 66 |and dist|ance Huf|
|00000900| 66 6d 61 6e 20 63 6f 64 | 65 73 20 74 68 61 74 20 |fman cod|es that |
|00000910| 61 72 65 0d 20 20 20 74 | 6f 20 62 65 20 75 73 65 |are. t|o be use|
|00000920| 64 20 74 6f 20 64 65 63 | 6f 64 65 20 74 68 69 73 |d to dec|ode this|
|00000930| 20 62 6c 6f 63 6b 2e 20 | 20 54 68 65 20 72 65 70 | block. | The rep|
|00000940| 72 65 73 65 6e 74 61 74 | 69 6f 6e 20 69 73 20 69 |resentat|ion is i|
|00000950| 74 73 65 6c 66 20 48 75 | 66 66 6d 61 6e 0d 20 20 |tself Hu|ffman. |
|00000960| 20 63 6f 64 65 64 2c 20 | 61 6e 64 20 73 6f 20 69 | coded, |and so i|
|00000970| 73 20 70 72 65 63 65 64 | 65 64 20 62 79 20 61 20 |s preced|ed by a |
|00000980| 64 65 73 63 72 69 70 74 | 69 6f 6e 20 6f 66 20 74 |descript|ion of t|
|00000990| 68 61 74 20 63 6f 64 65 | 2e 20 20 54 68 65 73 65 |hat code|. These|
|000009a0| 20 63 6f 64 65 0d 20 20 | 20 64 65 73 63 72 69 70 | code. | descrip|
|000009b0| 74 69 6f 6e 73 20 74 61 | 6b 65 20 75 70 20 61 20 |tions ta|ke up a |
|000009c0| 6c 69 74 74 6c 65 20 73 | 70 61 63 65 2c 20 61 6e |little s|pace, an|
|000009d0| 64 20 73 6f 20 66 6f 72 | 20 73 6d 61 6c 6c 20 62 |d so for| small b|
|000009e0| 6c 6f 63 6b 73 2c 20 74 | 68 65 72 65 20 69 73 0d |locks, t|here is.|
|000009f0| 20 20 20 61 20 70 72 65 | 64 65 66 69 6e 65 64 20 | a pre|defined |
|00000a00| 73 65 74 20 6f 66 20 63 | 6f 64 65 73 2c 20 63 61 |set of c|odes, ca|
|00000a10| 6c 6c 65 64 20 74 68 65 | 20 66 69 78 65 64 20 63 |lled the| fixed c|
|00000a20| 6f 64 65 73 2e 20 20 54 | 68 65 20 66 69 78 65 64 |odes. T|he fixed|
|00000a30| 20 6d 65 74 68 6f 64 20 | 69 73 0d 20 20 20 75 73 | method |is. us|
|00000a40| 65 64 20 69 66 20 74 68 | 65 20 62 6c 6f 63 6b 20 |ed if th|e block |
|00000a50| 63 6f 64 65 73 20 75 70 | 20 73 6d 61 6c 6c 65 72 |codes up| smaller|
|00000a60| 20 74 68 61 74 20 77 61 | 79 20 28 75 73 75 61 6c | that wa|y (usual|
|00000a70| 6c 79 20 66 6f 72 20 71 | 75 69 74 65 20 73 6d 61 |ly for q|uite sma|
|00000a80| 6c 6c 0d 20 20 20 63 68 | 75 6e 6b 73 29 2c 20 6f |ll. ch|unks), o|
|00000a90| 74 68 65 72 77 69 73 65 | 20 74 68 65 20 64 79 6e |therwise| the dyn|
|00000aa0| 61 6d 69 63 20 6d 65 74 | 68 6f 64 20 69 73 20 75 |amic met|hod is u|
|00000ab0| 73 65 64 2e 20 20 49 6e | 20 74 68 65 20 6c 61 74 |sed. In| the lat|
|00000ac0| 74 65 72 20 63 61 73 65 | 2c 20 74 68 65 0d 20 20 |ter case|, the. |
|00000ad0| 20 63 6f 64 65 73 20 61 | 72 65 20 63 75 73 74 6f | codes a|re custo|
|00000ae0| 6d 69 7a 65 64 20 74 6f | 20 74 68 65 20 70 72 6f |mized to| the pro|
|00000af0| 62 61 62 69 6c 69 74 69 | 65 73 20 69 6e 20 74 68 |babiliti|es in th|
|00000b00| 65 20 63 75 72 72 65 6e | 74 20 62 6c 6f 63 6b 2c |e curren|t block,|
|00000b10| 20 61 6e 64 20 73 6f 0d | 20 20 20 63 61 6e 20 63 | and so.| can c|
|00000b20| 6f 64 65 20 69 74 20 6d | 75 63 68 20 62 65 74 74 |ode it m|uch bett|
|00000b30| 65 72 20 74 68 61 6e 20 | 74 68 65 20 70 72 65 2d |er than |the pre-|
|00000b40| 64 65 74 65 72 6d 69 6e | 65 64 20 66 69 78 65 64 |determin|ed fixed|
|00000b50| 20 63 6f 64 65 73 2e 0d | 20 0d 20 20 20 54 68 65 | codes..| . The|
|00000b60| 20 48 75 66 66 6d 61 6e | 20 63 6f 64 65 73 20 74 | Huffman| codes t|
|00000b70| 68 65 6d 73 65 6c 76 65 | 73 20 61 72 65 20 64 65 |hemselve|s are de|
|00000b80| 63 6f 64 65 64 20 75 73 | 69 6e 67 20 61 20 6d 75 |coded us|ing a mu|
|00000b90| 74 6c 69 2d 6c 65 76 65 | 6c 20 74 61 62 6c 65 0d |tli-leve|l table.|
|00000ba0| 20 20 20 6c 6f 6f 6b 75 | 70 2c 20 69 6e 20 6f 72 | looku|p, in or|
|00000bb0| 64 65 72 20 74 6f 20 6d | 61 78 69 6d 69 7a 65 20 |der to m|aximize |
|00000bc0| 74 68 65 20 73 70 65 65 | 64 20 6f 66 20 64 65 63 |the spee|d of dec|
|00000bd0| 6f 64 69 6e 67 20 70 6c | 75 73 20 74 68 65 20 73 |oding pl|us the s|
|00000be0| 70 65 65 64 20 6f 66 0d | 20 20 20 62 75 69 6c 64 |peed of.| build|
|00000bf0| 69 6e 67 20 74 68 65 20 | 64 65 63 6f 64 69 6e 67 |ing the |decoding|
|00000c00| 20 74 61 62 6c 65 73 2e | 20 20 53 65 65 20 74 68 | tables.| See th|
|00000c10| 65 20 63 6f 6d 6d 65 6e | 74 73 20 62 65 6c 6f 77 |e commen|ts below|
|00000c20| 20 74 68 61 74 20 70 72 | 65 63 65 64 65 20 74 68 | that pr|ecede th|
|00000c30| 65 0d 20 20 20 6c 62 69 | 74 73 20 61 6e 64 20 64 |e. lbi|ts and d|
|00000c40| 62 69 74 73 20 74 75 6e | 69 6e 67 20 70 61 72 61 |bits tun|ing para|
|00000c50| 6d 65 74 65 72 73 2e 0d | 20 2a 2f 0d 0d 0d 2f 2a |meters..| */.../*|
|00000c60| 0d 20 20 20 4e 6f 74 65 | 73 20 62 65 79 6f 6e 64 |. Note|s beyond|
|00000c70| 20 74 68 65 20 31 2e 39 | 33 61 20 61 70 70 6e 6f | the 1.9|3a appno|
|00000c80| 74 65 2e 74 78 74 3a 0d | 0d 20 20 20 31 2e 20 44 |te.txt:.|. 1. D|
|00000c90| 69 73 74 61 6e 63 65 20 | 70 6f 69 6e 74 65 72 73 |istance |pointers|
|00000ca0| 20 6e 65 76 65 72 20 70 | 6f 69 6e 74 20 62 65 66 | never p|oint bef|
|00000cb0| 6f 72 65 20 74 68 65 20 | 62 65 67 69 6e 6e 69 6e |ore the |beginnin|
|00000cc0| 67 20 6f 66 20 74 68 65 | 20 6f 75 74 70 75 74 0d |g of the| output.|
|00000cd0| 20 20 20 20 20 20 73 74 | 72 65 61 6d 2e 0d 20 20 | st|ream.. |
|00000ce0| 20 32 2e 20 44 69 73 74 | 61 6e 63 65 20 70 6f 69 | 2. Dist|ance poi|
|00000cf0| 6e 74 65 72 73 20 63 61 | 6e 20 70 6f 69 6e 74 20 |nters ca|n point |
|00000d00| 62 61 63 6b 20 61 63 72 | 6f 73 73 20 62 6c 6f 63 |back acr|oss bloc|
|00000d10| 6b 73 2c 20 75 70 20 74 | 6f 20 33 32 6b 20 61 77 |ks, up t|o 32k aw|
|00000d20| 61 79 2e 0d 20 20 20 33 | 2e 20 54 68 65 72 65 20 |ay.. 3|. There |
|00000d30| 69 73 20 61 6e 20 69 6d | 70 6c 69 65 64 20 6d 61 |is an im|plied ma|
|00000d40| 78 69 6d 75 6d 20 6f 66 | 20 37 20 62 69 74 73 20 |ximum of| 7 bits |
|00000d50| 66 6f 72 20 74 68 65 20 | 62 69 74 20 6c 65 6e 67 |for the |bit leng|
|00000d60| 74 68 20 74 61 62 6c 65 | 20 61 6e 64 0d 20 20 20 |th table| and. |
|00000d70| 20 20 20 31 35 20 62 69 | 74 73 20 66 6f 72 20 74 | 15 bi|ts for t|
|00000d80| 68 65 20 61 63 74 75 61 | 6c 20 64 61 74 61 2e 0d |he actua|l data..|
|00000d90| 20 20 20 34 2e 20 49 66 | 20 6f 6e 6c 79 20 6f 6e | 4. If| only on|
|00000da0| 65 20 63 6f 64 65 20 65 | 78 69 73 74 73 2c 20 74 |e code e|xists, t|
|00000db0| 68 65 6e 20 69 74 20 69 | 73 20 65 6e 63 6f 64 65 |hen it i|s encode|
|00000dc0| 64 20 75 73 69 6e 67 20 | 6f 6e 65 20 62 69 74 2e |d using |one bit.|
|00000dd0| 20 20 28 5a 65 72 6f 0d | 20 20 20 20 20 20 77 6f | (Zero.| wo|
|00000de0| 75 6c 64 20 62 65 20 6d | 6f 72 65 20 65 66 66 69 |uld be m|ore effi|
|00000df0| 63 69 65 6e 74 2c 20 62 | 75 74 20 70 65 72 68 61 |cient, b|ut perha|
|00000e00| 70 73 20 61 20 6c 69 74 | 74 6c 65 20 63 6f 6e 66 |ps a lit|tle conf|
|00000e10| 75 73 69 6e 67 2e 29 20 | 20 49 66 20 74 77 6f 0d |using.) | If two.|
|00000e20| 20 20 20 20 20 20 63 6f | 64 65 73 20 65 78 69 73 | co|des exis|
|00000e30| 74 2c 20 74 68 65 79 20 | 61 72 65 20 63 6f 64 65 |t, they |are code|
|00000e40| 64 20 75 73 69 6e 67 20 | 6f 6e 65 20 62 69 74 20 |d using |one bit |
|00000e50| 65 61 63 68 20 28 30 20 | 61 6e 64 20 31 29 2e 0d |each (0 |and 1)..|
|00000e60| 20 20 20 35 2e 20 54 68 | 65 72 65 20 69 73 20 6e | 5. Th|ere is n|
|00000e70| 6f 20 77 61 79 20 6f 66 | 20 73 65 6e 64 69 6e 67 |o way of| sending|
|00000e80| 20 7a 65 72 6f 20 64 69 | 73 74 61 6e 63 65 20 63 | zero di|stance c|
|00000e90| 6f 64 65 73 2d 2d 61 20 | 64 75 6d 6d 79 20 6d 75 |odes--a |dummy mu|
|00000ea0| 73 74 20 62 65 0d 20 20 | 20 20 20 20 73 65 6e 74 |st be. | sent|
|00000eb0| 20 69 66 20 74 68 65 72 | 65 20 61 72 65 20 6e 6f | if ther|e are no|
|00000ec0| 6e 65 2e 20 20 28 48 69 | 73 74 6f 72 79 3a 20 61 |ne. (Hi|story: a|
|00000ed0| 20 70 72 65 20 32 2e 30 | 20 76 65 72 73 69 6f 6e | pre 2.0| version|
|00000ee0| 20 6f 66 20 50 4b 5a 49 | 50 20 77 6f 75 6c 64 0d | of PKZI|P would.|
|00000ef0| 20 20 20 20 20 20 73 74 | 6f 72 65 20 62 6c 6f 63 | st|ore bloc|
|00000f00| 6b 73 20 77 69 74 68 20 | 6e 6f 20 64 69 73 74 61 |ks with |no dista|
|00000f10| 6e 63 65 20 63 6f 64 65 | 73 2c 20 62 75 74 20 74 |nce code|s, but t|
|00000f20| 68 69 73 20 77 61 73 20 | 64 69 73 63 6f 76 65 72 |his was |discover|
|00000f30| 65 64 20 74 6f 20 62 65 | 0d 20 20 20 20 20 20 74 |ed to be|. t|
|00000f40| 6f 6f 20 68 61 72 73 68 | 20 61 20 63 72 69 74 65 |oo harsh| a crite|
|00000f50| 72 69 6f 6e 2e 29 20 20 | 56 61 6c 69 64 20 6f 6e |rion.) |Valid on|
|00000f60| 6c 79 20 66 6f 72 20 31 | 2e 39 33 61 2e 20 20 32 |ly for 1|.93a. 2|
|00000f70| 2e 30 34 63 20 64 6f 65 | 73 20 61 6c 6c 6f 77 0d |.04c doe|s allow.|
|00000f80| 20 20 20 20 20 20 7a 65 | 72 6f 20 64 69 73 74 61 | ze|ro dista|
|00000f90| 6e 63 65 20 63 6f 64 65 | 73 2c 20 77 68 69 63 68 |nce code|s, which|
|00000fa0| 20 69 73 20 73 65 6e 74 | 20 61 73 20 6f 6e 65 20 | is sent| as one |
|00000fb0| 63 6f 64 65 20 6f 66 20 | 7a 65 72 6f 20 62 69 74 |code of |zero bit|
|00000fc0| 73 20 69 6e 0d 20 20 20 | 20 20 20 6c 65 6e 67 74 |s in. | lengt|
|00000fd0| 68 2e 0d 20 20 20 36 2e | 20 54 68 65 72 65 20 61 |h.. 6.| There a|
|00000fe0| 72 65 20 75 70 20 74 6f | 20 32 38 36 20 6c 69 74 |re up to| 286 lit|
|00000ff0| 65 72 61 6c 2f 6c 65 6e | 67 74 68 20 63 6f 64 65 |eral/len|gth code|
|00001000| 73 2e 20 20 43 6f 64 65 | 20 32 35 36 20 72 65 70 |s. Code| 256 rep|
|00001010| 72 65 73 65 6e 74 73 20 | 74 68 65 0d 20 20 20 20 |resents |the. |
|00001020| 20 20 65 6e 64 2d 6f 66 | 2d 62 6c 6f 63 6b 2e 20 | end-of|-block. |
|00001030| 20 4e 6f 74 65 20 68 6f | 77 65 76 65 72 20 74 68 | Note ho|wever th|
|00001040| 61 74 20 74 68 65 20 73 | 74 61 74 69 63 20 6c 65 |at the s|tatic le|
|00001050| 6e 67 74 68 20 74 72 65 | 65 20 64 65 66 69 6e 65 |ngth tre|e define|
|00001060| 73 0d 20 20 20 20 20 20 | 32 38 38 20 63 6f 64 65 |s. |288 code|
|00001070| 73 20 6a 75 73 74 20 74 | 6f 20 66 69 6c 6c 20 6f |s just t|o fill o|
|00001080| 75 74 20 74 68 65 20 48 | 75 66 66 6d 61 6e 20 63 |ut the H|uffman c|
|00001090| 6f 64 65 73 2e 20 20 43 | 6f 64 65 73 20 32 38 36 |odes. C|odes 286|
|000010a0| 20 61 6e 64 20 32 38 37 | 0d 20 20 20 20 20 20 63 | and 287|. c|
|000010b0| 61 6e 6e 6f 74 20 62 65 | 20 75 73 65 64 20 74 68 |annot be| used th|
|000010c0| 6f 75 67 68 2c 20 73 69 | 6e 63 65 20 74 68 65 72 |ough, si|nce ther|
|000010d0| 65 20 69 73 20 6e 6f 20 | 6c 65 6e 67 74 68 20 62 |e is no |length b|
|000010e0| 61 73 65 20 6f 72 20 65 | 78 74 72 61 20 62 69 74 |ase or e|xtra bit|
|000010f0| 73 0d 20 20 20 20 20 20 | 64 65 66 69 6e 65 64 20 |s. |defined |
|00001100| 66 6f 72 20 74 68 65 6d | 2e 20 20 53 69 6d 69 6c |for them|. Simil|
|00001110| 61 72 6c 79 2c 20 74 68 | 65 72 65 20 61 72 65 20 |arly, th|ere are |
|00001120| 75 70 20 74 6f 20 33 30 | 20 64 69 73 74 61 6e 63 |up to 30| distanc|
|00001130| 65 20 63 6f 64 65 73 2e | 0d 20 20 20 20 20 20 48 |e codes.|. H|
|00001140| 6f 77 65 76 65 72 2c 20 | 73 74 61 74 69 63 20 74 |owever, |static t|
|00001150| 72 65 65 73 20 64 65 66 | 69 6e 65 20 33 32 20 63 |rees def|ine 32 c|
|00001160| 6f 64 65 73 20 28 61 6c | 6c 20 35 20 62 69 74 73 |odes (al|l 5 bits|
|00001170| 29 20 74 6f 20 66 69 6c | 6c 20 6f 75 74 20 74 68 |) to fil|l out th|
|00001180| 65 0d 20 20 20 20 20 20 | 48 75 66 66 6d 61 6e 20 |e. |Huffman |
|00001190| 63 6f 64 65 73 2c 20 62 | 75 74 20 74 68 65 20 6c |codes, b|ut the l|
|000011a0| 61 73 74 20 74 77 6f 20 | 68 61 64 20 62 65 74 74 |ast two |had bett|
|000011b0| 65 72 20 6e 6f 74 20 73 | 68 6f 77 20 75 70 20 69 |er not s|how up i|
|000011c0| 6e 20 74 68 65 20 64 61 | 74 61 2e 0d 20 20 20 37 |n the da|ta.. 7|
|000011d0| 2e 20 55 6e 7a 69 70 20 | 63 61 6e 20 63 68 65 63 |. Unzip |can chec|
|000011e0| 6b 20 64 79 6e 61 6d 69 | 63 20 48 75 66 66 6d 61 |k dynami|c Huffma|
|000011f0| 6e 20 62 6c 6f 63 6b 73 | 20 66 6f 72 20 63 6f 6d |n blocks| for com|
|00001200| 70 6c 65 74 65 20 63 6f | 64 65 20 73 65 74 73 2e |plete co|de sets.|
|00001210| 0d 20 20 20 20 20 20 54 | 68 65 20 65 78 63 65 70 |. T|he excep|
|00001220| 74 69 6f 6e 20 69 73 20 | 74 68 61 74 20 61 20 73 |tion is |that a s|
|00001230| 69 6e 67 6c 65 20 63 6f | 64 65 20 77 6f 75 6c 64 |ingle co|de would|
|00001240| 20 6e 6f 74 20 62 65 20 | 63 6f 6d 70 6c 65 74 65 | not be |complete|
|00001250| 20 28 73 65 65 20 23 34 | 29 2e 0d 20 20 20 38 2e | (see #4|).. 8.|
|00001260| 20 54 68 65 20 66 69 76 | 65 20 62 69 74 73 20 66 | The fiv|e bits f|
|00001270| 6f 6c 6c 6f 77 69 6e 67 | 20 74 68 65 20 62 6c 6f |ollowing| the blo|
|00001280| 63 6b 20 74 79 70 65 20 | 69 73 20 72 65 61 6c 6c |ck type |is reall|
|00001290| 79 20 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 0d |y the nu|mber of.|
|000012a0| 20 20 20 20 20 20 6c 69 | 74 65 72 61 6c 20 63 6f | li|teral co|
|000012b0| 64 65 73 20 73 65 6e 74 | 20 6d 69 6e 75 73 20 32 |des sent| minus 2|
|000012c0| 35 37 2e 0d 20 20 20 39 | 2e 20 4c 65 6e 67 74 68 |57.. 9|. Length|
|000012d0| 20 63 6f 64 65 73 20 38 | 2c 31 36 2c 31 36 20 61 | codes 8|,16,16 a|
|000012e0| 72 65 20 69 6e 74 65 72 | 70 72 65 74 65 64 20 61 |re inter|preted a|
|000012f0| 73 20 31 33 20 6c 65 6e | 67 74 68 20 63 6f 64 65 |s 13 len|gth code|
|00001300| 73 20 6f 66 20 38 20 62 | 69 74 73 0d 20 20 20 20 |s of 8 b|its. |
|00001310| 20 20 28 31 2b 36 2b 36 | 29 2e 20 20 54 68 65 72 | (1+6+6|). Ther|
|00001320| 65 66 6f 72 65 2c 20 74 | 6f 20 6f 75 74 70 75 74 |efore, t|o output|
|00001330| 20 74 68 72 65 65 20 74 | 69 6d 65 73 20 74 68 65 | three t|imes the|
|00001340| 20 6c 65 6e 67 74 68 2c | 20 79 6f 75 20 6f 75 74 | length,| you out|
|00001350| 70 75 74 0d 20 20 20 20 | 20 20 74 68 72 65 65 20 |put. | three |
|00001360| 63 6f 64 65 73 20 28 31 | 2b 31 2b 31 29 2c 20 77 |codes (1|+1+1), w|
|00001370| 68 65 72 65 61 73 20 74 | 6f 20 6f 75 74 70 75 74 |hereas t|o output|
|00001380| 20 66 6f 75 72 20 74 69 | 6d 65 73 20 74 68 65 20 | four ti|mes the |
|00001390| 73 61 6d 65 20 6c 65 6e | 67 74 68 2c 0d 20 20 20 |same len|gth,. |
|000013a0| 20 20 20 79 6f 75 20 6f | 6e 6c 79 20 6e 65 65 64 | you o|nly need|
|000013b0| 20 74 77 6f 20 63 6f 64 | 65 73 20 28 31 2b 33 29 | two cod|es (1+3)|
|000013c0| 2e 20 20 48 6d 6d 2e 0d | 20 20 31 30 2e 20 49 6e |. Hmm..| 10. In|
|000013d0| 20 74 68 65 20 74 72 65 | 65 20 72 65 63 6f 6e 73 | the tre|e recons|
|000013e0| 74 72 75 63 74 69 6f 6e | 20 61 6c 67 6f 72 69 74 |truction| algorit|
|000013f0| 68 6d 2c 20 43 6f 64 65 | 20 3d 20 43 6f 64 65 20 |hm, Code| = Code |
|00001400| 2b 20 49 6e 63 72 65 6d | 65 6e 74 0d 20 20 20 20 |+ Increm|ent. |
|00001410| 20 20 6f 6e 6c 79 20 69 | 66 20 42 69 74 4c 65 6e | only i|f BitLen|
|00001420| 67 74 68 28 69 29 20 69 | 73 20 6e 6f 74 20 7a 65 |gth(i) i|s not ze|
|00001430| 72 6f 2e 20 20 28 50 72 | 65 74 74 79 20 6f 62 76 |ro. (Pr|etty obv|
|00001440| 69 6f 75 73 2e 29 0d 20 | 20 31 31 2e 20 43 6f 72 |ious.). | 11. Cor|
|00001450| 72 65 63 74 69 6f 6e 3a | 20 34 20 42 69 74 73 3a |rection:| 4 Bits:|
|00001460| 20 23 20 6f 66 20 42 69 | 74 20 4c 65 6e 67 74 68 | # of Bi|t Length|
|00001470| 20 63 6f 64 65 73 20 2d | 20 34 20 20 20 20 20 28 | codes -| 4 (|
|00001480| 34 20 2d 20 31 39 29 0d | 20 20 31 32 2e 20 4e 6f |4 - 19).| 12. No|
|00001490| 74 65 3a 20 6c 65 6e 67 | 74 68 20 63 6f 64 65 20 |te: leng|th code |
|000014a0| 32 38 34 20 63 61 6e 20 | 72 65 70 72 65 73 65 6e |284 can |represen|
|000014b0| 74 20 32 32 37 2d 32 35 | 38 2c 20 62 75 74 20 6c |t 227-25|8, but l|
|000014c0| 65 6e 67 74 68 20 63 6f | 64 65 20 32 38 35 0d 20 |ength co|de 285. |
|000014d0| 20 20 20 20 20 72 65 61 | 6c 6c 79 20 69 73 20 32 | rea|lly is 2|
|000014e0| 35 38 2e 20 20 54 68 65 | 20 6c 61 73 74 20 6c 65 |58. The| last le|
|000014f0| 6e 67 74 68 20 64 65 73 | 65 72 76 65 73 20 69 74 |ngth des|erves it|
|00001500| 73 20 6f 77 6e 2c 20 73 | 68 6f 72 74 20 63 6f 64 |s own, s|hort cod|
|00001510| 65 0d 20 20 20 20 20 20 | 73 69 6e 63 65 20 69 74 |e. |since it|
|00001520| 20 67 65 74 73 20 75 73 | 65 64 20 61 20 6c 6f 74 | gets us|ed a lot|
|00001530| 20 69 6e 20 76 65 72 79 | 20 72 65 64 75 6e 64 61 | in very| redunda|
|00001540| 6e 74 20 66 69 6c 65 73 | 2e 20 20 54 68 65 20 6c |nt files|. The l|
|00001550| 65 6e 67 74 68 0d 20 20 | 20 20 20 20 32 35 38 20 |ength. | 258 |
|00001560| 69 73 20 73 70 65 63 69 | 61 6c 20 73 69 6e 63 65 |is speci|al since|
|00001570| 20 32 35 38 20 2d 20 33 | 20 28 74 68 65 20 6d 69 | 258 - 3| (the mi|
|00001580| 6e 20 6d 61 74 63 68 20 | 6c 65 6e 67 74 68 29 20 |n match |length) |
|00001590| 69 73 20 32 35 35 2e 0d | 20 20 31 33 2e 20 54 68 |is 255..| 13. Th|
|000015a0| 65 20 6c 69 74 65 72 61 | 6c 2f 6c 65 6e 67 74 68 |e litera|l/length|
|000015b0| 20 61 6e 64 20 64 69 73 | 74 61 6e 63 65 20 63 6f | and dis|tance co|
|000015c0| 64 65 20 62 69 74 20 6c | 65 6e 67 74 68 73 20 61 |de bit l|engths a|
|000015d0| 72 65 20 72 65 61 64 20 | 61 73 20 61 0d 20 20 20 |re read |as a. |
|000015e0| 20 20 20 73 69 6e 67 6c | 65 20 73 74 72 65 61 6d | singl|e stream|
|000015f0| 20 6f 66 20 6c 65 6e 67 | 74 68 73 2e 20 20 49 74 | of leng|ths. It|
|00001600| 20 69 73 20 70 6f 73 73 | 69 62 6c 65 20 28 61 6e | is poss|ible (an|
|00001610| 64 20 61 64 76 61 6e 74 | 61 67 65 6f 75 73 29 20 |d advant|ageous) |
|00001620| 66 6f 72 0d 20 20 20 20 | 20 20 61 20 72 65 70 65 |for. | a repe|
|00001630| 61 74 20 63 6f 64 65 20 | 28 31 36 2c 20 31 37 2c |at code |(16, 17,|
|00001640| 20 6f 72 20 31 38 29 20 | 74 6f 20 67 6f 20 61 63 | or 18) |to go ac|
|00001650| 72 6f 73 73 20 74 68 65 | 20 62 6f 75 6e 64 61 72 |ross the| boundar|
|00001660| 79 20 62 65 74 77 65 65 | 6e 0d 20 20 20 20 20 20 |y betwee|n. |
|00001670| 74 68 65 20 74 77 6f 20 | 73 65 74 73 20 6f 66 20 |the two |sets of |
|00001680| 6c 65 6e 67 74 68 73 2e | 0d 20 2a 2f 0d 0d 23 69 |lengths.|. */..#i|
|00001690| 66 64 65 66 20 52 43 53 | 49 44 0d 73 74 61 74 69 |fdef RCS|ID.stati|
|000016a0| 63 20 63 68 61 72 20 72 | 63 73 69 64 5b 5d 20 3d |c char r|csid[] =|
|000016b0| 20 22 24 49 64 3a 20 69 | 6e 66 6c 61 74 65 2e 63 | "$Id: i|nflate.c|
|000016c0| 2c 76 20 30 2e 31 34 20 | 31 39 39 33 2f 30 36 2f |,v 0.14 |1993/06/|
|000016d0| 31 30 20 31 33 3a 32 37 | 3a 30 34 20 6a 6c 6f 75 |10 13:27|:04 jlou|
|000016e0| 70 20 45 78 70 20 24 22 | 3b 0d 23 65 6e 64 69 66 |p Exp $"|;.#endif|
|000016f0| 0d 0d 23 69 6e 63 6c 75 | 64 65 20 3c 73 79 73 2f |..#inclu|de <sys/|
|00001700| 74 79 70 65 73 2e 68 3e | 0d 0d 23 69 6e 63 6c 75 |types.h>|..#inclu|
|00001710| 64 65 20 22 74 61 69 6c | 6f 72 2e 68 22 0d 0d 23 |de "tail|or.h"..#|
|00001720| 69 66 20 64 65 66 69 6e | 65 64 28 53 54 44 43 5f |if defin|ed(STDC_|
|00001730| 48 45 41 44 45 52 53 29 | 20 7c 7c 20 21 64 65 66 |HEADERS)| || !def|
|00001740| 69 6e 65 64 28 4e 4f 5f | 53 54 44 4c 49 42 5f 48 |ined(NO_|STDLIB_H|
|00001750| 29 0d 23 20 20 69 6e 63 | 6c 75 64 65 20 3c 73 74 |).# inc|lude <st|
|00001760| 64 6c 69 62 2e 68 3e 0d | 23 65 6e 64 69 66 0d 0d |dlib.h>.|#endif..|
|00001770| 23 69 6e 63 6c 75 64 65 | 20 22 67 7a 69 70 2e 68 |#include| "gzip.h|
|00001780| 22 0d 23 64 65 66 69 6e | 65 20 73 6c 69 64 65 20 |".#defin|e slide |
|00001790| 77 69 6e 64 6f 77 0d 0d | 23 69 6e 63 6c 75 64 65 |window..|#include|
|000017a0| 20 22 4d 61 63 45 72 72 | 6f 72 73 2e 68 22 0d 0d | "MacErr|ors.h"..|
|000017b0| 2f 2a 20 48 75 66 66 6d | 61 6e 20 63 6f 64 65 20 |/* Huffm|an code |
|000017c0| 6c 6f 6f 6b 75 70 20 74 | 61 62 6c 65 20 65 6e 74 |lookup t|able ent|
|000017d0| 72 79 2d 2d 74 68 69 73 | 20 65 6e 74 72 79 20 69 |ry--this| entry i|
|000017e0| 73 20 66 6f 75 72 20 62 | 79 74 65 73 20 66 6f 72 |s four b|ytes for|
|000017f0| 20 6d 61 63 68 69 6e 65 | 73 0d 20 20 20 74 68 61 | machine|s. tha|
|00001800| 74 20 68 61 76 65 20 31 | 36 2d 62 69 74 20 70 6f |t have 1|6-bit po|
|00001810| 69 6e 74 65 72 73 20 28 | 65 2e 67 2e 20 50 43 27 |inters (|e.g. PC'|
|00001820| 73 20 69 6e 20 74 68 65 | 20 73 6d 61 6c 6c 20 6f |s in the| small o|
|00001830| 72 20 6d 65 64 69 75 6d | 20 6d 6f 64 65 6c 29 2e |r medium| model).|
|00001840| 0d 20 20 20 56 61 6c 69 | 64 20 65 78 74 72 61 20 |. Vali|d extra |
|00001850| 62 69 74 73 20 61 72 65 | 20 30 2e 2e 31 33 2e 20 |bits are| 0..13. |
|00001860| 20 65 20 3d 3d 20 31 35 | 20 69 73 20 45 4f 42 20 | e == 15| is EOB |
|00001870| 28 65 6e 64 20 6f 66 20 | 62 6c 6f 63 6b 29 2c 20 |(end of |block), |
|00001880| 65 20 3d 3d 20 31 36 0d | 20 20 20 6d 65 61 6e 73 |e == 16.| means|
|00001890| 20 74 68 61 74 20 76 20 | 69 73 20 61 20 6c 69 74 | that v |is a lit|
|000018a0| 65 72 61 6c 2c 20 31 36 | 20 3c 20 65 20 3c 20 33 |eral, 16| < e < 3|
|000018b0| 32 20 6d 65 61 6e 73 20 | 74 68 61 74 20 76 20 69 |2 means |that v i|
|000018c0| 73 20 61 20 70 6f 69 6e | 74 65 72 20 74 6f 0d 20 |s a poin|ter to. |
|000018d0| 20 20 74 68 65 20 6e 65 | 78 74 20 74 61 62 6c 65 | the ne|xt table|
|000018e0| 2c 20 77 68 69 63 68 20 | 63 6f 64 65 73 20 65 20 |, which |codes e |
|000018f0| 2d 20 31 36 20 62 69 74 | 73 2c 20 61 6e 64 20 6c |- 16 bit|s, and l|
|00001900| 61 73 74 6c 79 20 65 20 | 3d 3d 20 39 39 20 69 6e |astly e |== 99 in|
|00001910| 64 69 63 61 74 65 73 0d | 20 20 20 61 6e 20 75 6e |dicates.| an un|
|00001920| 75 73 65 64 20 63 6f 64 | 65 2e 20 20 49 66 20 61 |used cod|e. If a|
|00001930| 20 63 6f 64 65 20 77 69 | 74 68 20 65 20 3d 3d 20 | code wi|th e == |
|00001940| 39 39 20 69 73 20 6c 6f | 6f 6b 65 64 20 75 70 2c |99 is lo|oked up,|
|00001950| 20 74 68 69 73 20 69 6d | 70 6c 69 65 73 20 61 6e | this im|plies an|
|00001960| 0d 20 20 20 65 72 72 6f | 72 20 69 6e 20 74 68 65 |. erro|r in the|
|00001970| 20 64 61 74 61 2e 20 2a | 2f 0d 73 74 72 75 63 74 | data. *|/.struct|
|00001980| 20 68 75 66 74 20 7b 0d | 20 20 75 63 68 20 65 3b | huft {.| uch e;|
|00001990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000019a0| 2f 2a 20 6e 75 6d 62 65 | 72 20 6f 66 20 65 78 74 |/* numbe|r of ext|
|000019b0| 72 61 20 62 69 74 73 20 | 6f 72 20 6f 70 65 72 61 |ra bits |or opera|
|000019c0| 74 69 6f 6e 20 2a 2f 0d | 20 20 75 63 68 20 62 3b |tion */.| uch b;|
|000019d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000019e0| 2f 2a 20 6e 75 6d 62 65 | 72 20 6f 66 20 62 69 74 |/* numbe|r of bit|
|000019f0| 73 20 69 6e 20 74 68 69 | 73 20 63 6f 64 65 20 6f |s in thi|s code o|
|00001a00| 72 20 73 75 62 63 6f 64 | 65 20 2a 2f 0d 20 20 75 |r subcod|e */. u|
|00001a10| 6e 69 6f 6e 20 7b 0d 20 | 20 20 20 75 73 68 20 6e |nion {. | ush n|
|00001a20| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |; | /|
|00001a30| 2a 20 6c 69 74 65 72 61 | 6c 2c 20 6c 65 6e 67 74 |* litera|l, lengt|
|00001a40| 68 20 62 61 73 65 2c 20 | 6f 72 20 64 69 73 74 61 |h base, |or dista|
|00001a50| 6e 63 65 20 62 61 73 65 | 20 2a 2f 0d 20 20 20 20 |nce base| */. |
|00001a60| 73 74 72 75 63 74 20 68 | 75 66 74 20 2a 74 3b 20 |struct h|uft *t; |
|00001a70| 20 20 20 20 2f 2a 20 70 | 6f 69 6e 74 65 72 20 74 | /* p|ointer t|
|00001a80| 6f 20 6e 65 78 74 20 6c | 65 76 65 6c 20 6f 66 20 |o next l|evel of |
|00001a90| 74 61 62 6c 65 20 2a 2f | 0d 20 20 7d 20 76 3b 0d |table */|. } v;.|
|00001aa0| 7d 3b 0d 0d 0d 2f 2a 20 | 46 75 6e 63 74 69 6f 6e |};.../* |Function|
|00001ab0| 20 70 72 6f 74 6f 74 79 | 70 65 73 20 2a 2f 0d 69 | prototy|pes */.i|
|00001ac0| 6e 74 20 68 75 66 74 5f | 62 75 69 6c 64 20 4f 46 |nt huft_|build OF|
|00001ad0| 28 28 75 6e 73 69 67 6e | 65 64 20 2a 2c 20 75 6e |((unsign|ed *, un|
|00001ae0| 73 69 67 6e 65 64 2c 20 | 75 6e 73 69 67 6e 65 64 |signed, |unsigned|
|00001af0| 2c 20 75 73 68 20 2a 2c | 20 75 73 68 20 2a 2c 0d |, ush *,| ush *,.|
|00001b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001b10| 20 20 20 73 74 72 75 63 | 74 20 68 75 66 74 20 2a | struc|t huft *|
|00001b20| 2a 2c 20 69 6e 74 20 2a | 29 29 3b 0d 69 6e 74 20 |*, int *|));.int |
|00001b30| 68 75 66 74 5f 66 72 65 | 65 20 4f 46 28 28 73 74 |huft_fre|e OF((st|
|00001b40| 72 75 63 74 20 68 75 66 | 74 20 2a 29 29 3b 0d 69 |ruct huf|t *));.i|
|00001b50| 6e 74 20 69 6e 66 6c 61 | 74 65 5f 63 6f 64 65 73 |nt infla|te_codes|
|00001b60| 20 4f 46 28 28 73 74 72 | 75 63 74 20 68 75 66 74 | OF((str|uct huft|
|00001b70| 20 2a 2c 20 73 74 72 75 | 63 74 20 68 75 66 74 20 | *, stru|ct huft |
|00001b80| 2a 2c 20 69 6e 74 2c 20 | 69 6e 74 29 29 3b 0d 69 |*, int, |int));.i|
|00001b90| 6e 74 20 69 6e 66 6c 61 | 74 65 5f 73 74 6f 72 65 |nt infla|te_store|
|00001ba0| 64 20 4f 46 28 28 76 6f | 69 64 29 29 3b 0d 69 6e |d OF((vo|id));.in|
|00001bb0| 74 20 69 6e 66 6c 61 74 | 65 5f 66 69 78 65 64 20 |t inflat|e_fixed |
|00001bc0| 4f 46 28 28 76 6f 69 64 | 29 29 3b 0d 69 6e 74 20 |OF((void|));.int |
|00001bd0| 69 6e 66 6c 61 74 65 5f | 64 79 6e 61 6d 69 63 20 |inflate_|dynamic |
|00001be0| 4f 46 28 28 76 6f 69 64 | 29 29 3b 0d 69 6e 74 20 |OF((void|));.int |
|00001bf0| 69 6e 66 6c 61 74 65 5f | 62 6c 6f 63 6b 20 4f 46 |inflate_|block OF|
|00001c00| 28 28 69 6e 74 20 2a 29 | 29 3b 0d 69 6e 74 20 69 |((int *)|);.int i|
|00001c10| 6e 66 6c 61 74 65 20 4f | 46 28 28 76 6f 69 64 29 |nflate O|F((void)|
|00001c20| 29 3b 0d 0d 0d 2f 2a 20 | 54 68 65 20 69 6e 66 6c |);.../* |The infl|
|00001c30| 61 74 65 20 61 6c 67 6f | 72 69 74 68 6d 20 75 73 |ate algo|rithm us|
|00001c40| 65 73 20 61 20 73 6c 69 | 64 69 6e 67 20 33 32 4b |es a sli|ding 32K|
|00001c50| 20 62 79 74 65 20 77 69 | 6e 64 6f 77 20 6f 6e 20 | byte wi|ndow on |
|00001c60| 74 68 65 20 75 6e 63 6f | 6d 70 72 65 73 73 65 64 |the unco|mpressed|
|00001c70| 0d 20 20 20 73 74 72 65 | 61 6d 20 74 6f 20 66 69 |. stre|am to fi|
|00001c80| 6e 64 20 72 65 70 65 61 | 74 65 64 20 62 79 74 65 |nd repea|ted byte|
|00001c90| 20 73 74 72 69 6e 67 73 | 2e 20 20 54 68 69 73 20 | strings|. This |
|00001ca0| 69 73 20 69 6d 70 6c 65 | 6d 65 6e 74 65 64 20 68 |is imple|mented h|
|00001cb0| 65 72 65 20 61 73 20 61 | 0d 20 20 20 63 69 72 63 |ere as a|. circ|
|00001cc0| 75 6c 61 72 20 62 75 66 | 66 65 72 2e 20 20 54 68 |ular buf|fer. Th|
|00001cd0| 65 20 69 6e 64 65 78 20 | 69 73 20 75 70 64 61 74 |e index |is updat|
|00001ce0| 65 64 20 73 69 6d 70 6c | 79 20 62 79 20 69 6e 63 |ed simpl|y by inc|
|00001cf0| 72 65 6d 65 6e 74 69 6e | 67 20 61 6e 64 20 74 68 |rementin|g and th|
|00001d00| 65 6e 0d 20 20 20 61 6e | 64 27 69 6e 67 20 77 69 |en. an|d'ing wi|
|00001d10| 74 68 20 30 78 37 66 66 | 66 20 28 33 32 4b 2d 31 |th 0x7ff|f (32K-1|
|00001d20| 29 2e 20 2a 2f 0d 2f 2a | 20 49 74 20 69 73 20 6c |). */./*| It is l|
|00001d30| 65 66 74 20 74 6f 20 6f | 74 68 65 72 20 6d 6f 64 |eft to o|ther mod|
|00001d40| 75 6c 65 73 20 74 6f 20 | 73 75 70 70 6c 79 20 74 |ules to |supply t|
|00001d50| 68 65 20 33 32 4b 20 61 | 72 65 61 2e 20 20 49 74 |he 32K a|rea. It|
|00001d60| 20 69 73 20 61 73 73 75 | 6d 65 64 0d 20 20 20 74 | is assu|med. t|
|00001d70| 6f 20 62 65 20 75 73 61 | 62 6c 65 20 61 73 20 69 |o be usa|ble as i|
|00001d80| 66 20 69 74 20 77 65 72 | 65 20 64 65 63 6c 61 72 |f it wer|e declar|
|00001d90| 65 64 20 22 75 63 68 20 | 73 6c 69 64 65 5b 33 32 |ed "uch |slide[32|
|00001da0| 37 36 38 5d 3b 22 20 6f | 72 20 61 73 20 6a 75 73 |768];" o|r as jus|
|00001db0| 74 0d 20 20 20 22 75 63 | 68 20 2a 73 6c 69 64 65 |t. "uc|h *slide|
|00001dc0| 3b 22 20 61 6e 64 20 74 | 68 65 6e 20 6d 61 6c 6c |;" and t|hen mall|
|00001dd0| 6f 63 27 65 64 20 69 6e | 20 74 68 65 20 6c 61 74 |oc'ed in| the lat|
|00001de0| 74 65 72 20 63 61 73 65 | 2e 20 20 54 68 65 20 64 |ter case|. The d|
|00001df0| 65 66 69 6e 69 74 69 6f | 6e 0d 20 20 20 6d 75 73 |efinitio|n. mus|
|00001e00| 74 20 62 65 20 69 6e 20 | 75 6e 7a 69 70 2e 68 2c |t be in |unzip.h,|
|00001e10| 20 69 6e 63 6c 75 64 65 | 64 20 61 62 6f 76 65 2e | include|d above.|
|00001e20| 20 2a 2f 0d 2f 2a 20 75 | 6e 73 69 67 6e 65 64 20 | */./* u|nsigned |
|00001e30| 77 70 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |wp; | |
|00001e40| 63 75 72 72 65 6e 74 20 | 70 6f 73 69 74 69 6f 6e |current |position|
|00001e50| 20 69 6e 20 73 6c 69 64 | 65 20 2a 2f 0d 23 64 65 | in slid|e */.#de|
|00001e60| 66 69 6e 65 20 77 70 20 | 6f 75 74 63 6e 74 0d 23 |fine wp |outcnt.#|
|00001e70| 64 65 66 69 6e 65 20 66 | 6c 75 73 68 5f 6f 75 74 |define f|lush_out|
|00001e80| 70 75 74 28 77 29 20 28 | 77 70 3d 28 77 29 2c 66 |put(w) (|wp=(w),f|
|00001e90| 6c 75 73 68 5f 77 69 6e | 64 6f 77 28 29 29 0d 0d |lush_win|dow())..|
|00001ea0| 2f 2a 20 54 61 62 6c 65 | 73 20 66 6f 72 20 64 65 |/* Table|s for de|
|00001eb0| 66 6c 61 74 65 20 66 72 | 6f 6d 20 50 4b 5a 49 50 |flate fr|om PKZIP|
|00001ec0| 27 73 20 61 70 70 6e 6f | 74 65 2e 74 78 74 2e 20 |'s appno|te.txt. |
|00001ed0| 2a 2f 0d 73 74 61 74 69 | 63 20 75 6e 73 69 67 6e |*/.stati|c unsign|
|00001ee0| 65 64 20 62 6f 72 64 65 | 72 5b 5d 20 3d 20 7b 20 |ed borde|r[] = { |
|00001ef0| 20 20 20 2f 2a 20 4f 72 | 64 65 72 20 6f 66 20 74 | /* Or|der of t|
|00001f00| 68 65 20 62 69 74 20 6c | 65 6e 67 74 68 20 63 6f |he bit l|ength co|
|00001f10| 64 65 20 6c 65 6e 67 74 | 68 73 20 2a 2f 0d 20 20 |de lengt|hs */. |
|00001f20| 20 20 20 20 20 20 31 36 | 2c 20 31 37 2c 20 31 38 | 16|, 17, 18|
|00001f30| 2c 20 30 2c 20 38 2c 20 | 37 2c 20 39 2c 20 36 2c |, 0, 8, |7, 9, 6,|
|00001f40| 20 31 30 2c 20 35 2c 20 | 31 31 2c 20 34 2c 20 31 | 10, 5, |11, 4, 1|
|00001f50| 32 2c 20 33 2c 20 31 33 | 2c 20 32 2c 20 31 34 2c |2, 3, 13|, 2, 14,|
|00001f60| 20 31 2c 20 31 35 7d 3b | 0d 73 74 61 74 69 63 20 | 1, 15};|.static |
|00001f70| 75 73 68 20 63 70 6c 65 | 6e 73 5b 5d 20 3d 20 7b |ush cple|ns[] = {|
|00001f80| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 43 6f 70 79 | | /* Copy|
|00001f90| 20 6c 65 6e 67 74 68 73 | 20 66 6f 72 20 6c 69 74 | lengths| for lit|
|00001fa0| 65 72 61 6c 20 63 6f 64 | 65 73 20 32 35 37 2e 2e |eral cod|es 257..|
|00001fb0| 32 38 35 20 2a 2f 0d 20 | 20 20 20 20 20 20 20 33 |285 */. | 3|
|00001fc0| 2c 20 34 2c 20 35 2c 20 | 36 2c 20 37 2c 20 38 2c |, 4, 5, |6, 7, 8,|
|00001fd0| 20 39 2c 20 31 30 2c 20 | 31 31 2c 20 31 33 2c 20 | 9, 10, |11, 13, |
|00001fe0| 31 35 2c 20 31 37 2c 20 | 31 39 2c 20 32 33 2c 20 |15, 17, |19, 23, |
|00001ff0| 32 37 2c 20 33 31 2c 0d | 20 20 20 20 20 20 20 20 |27, 31,.| |
|00002000| 33 35 2c 20 34 33 2c 20 | 35 31 2c 20 35 39 2c 20 |35, 43, |51, 59, |
|00002010| 36 37 2c 20 38 33 2c 20 | 39 39 2c 20 31 31 35 2c |67, 83, |99, 115,|
|00002020| 20 31 33 31 2c 20 31 36 | 33 2c 20 31 39 35 2c 20 | 131, 16|3, 195, |
|00002030| 32 32 37 2c 20 32 35 38 | 2c 20 30 2c 20 30 7d 3b |227, 258|, 0, 0};|
|00002040| 0d 20 20 20 20 20 20 20 | 20 2f 2a 20 6e 6f 74 65 |. | /* note|
|00002050| 3a 20 73 65 65 20 6e 6f | 74 65 20 23 31 33 20 61 |: see no|te #13 a|
|00002060| 62 6f 76 65 20 61 62 6f | 75 74 20 74 68 65 20 32 |bove abo|ut the 2|
|00002070| 35 38 20 69 6e 20 74 68 | 69 73 20 6c 69 73 74 2e |58 in th|is list.|
|00002080| 20 2a 2f 0d 73 74 61 74 | 69 63 20 75 73 68 20 63 | */.stat|ic ush c|
|00002090| 70 6c 65 78 74 5b 5d 20 | 3d 20 7b 20 20 20 20 20 |plext[] |= { |
|000020a0| 20 20 20 20 2f 2a 20 45 | 78 74 72 61 20 62 69 74 | /* E|xtra bit|
|000020b0| 73 20 66 6f 72 20 6c 69 | 74 65 72 61 6c 20 63 6f |s for li|teral co|
|000020c0| 64 65 73 20 32 35 37 2e | 2e 32 38 35 20 2a 2f 0d |des 257.|.285 */.|
|000020d0| 20 20 20 20 20 20 20 20 | 30 2c 20 30 2c 20 30 2c | |0, 0, 0,|
|000020e0| 20 30 2c 20 30 2c 20 30 | 2c 20 30 2c 20 30 2c 20 | 0, 0, 0|, 0, 0, |
|000020f0| 31 2c 20 31 2c 20 31 2c | 20 31 2c 20 32 2c 20 32 |1, 1, 1,| 1, 2, 2|
|00002100| 2c 20 32 2c 20 32 2c 0d | 20 20 20 20 20 20 20 20 |, 2, 2,.| |
|00002110| 33 2c 20 33 2c 20 33 2c | 20 33 2c 20 34 2c 20 34 |3, 3, 3,| 3, 4, 4|
|00002120| 2c 20 34 2c 20 34 2c 20 | 35 2c 20 35 2c 20 35 2c |, 4, 4, |5, 5, 5,|
|00002130| 20 35 2c 20 30 2c 20 39 | 39 2c 20 39 39 7d 3b 20 | 5, 0, 9|9, 99}; |
|00002140| 2f 2a 20 39 39 3d 3d 69 | 6e 76 61 6c 69 64 20 2a |/* 99==i|nvalid *|
|00002150| 2f 0d 73 74 61 74 69 63 | 20 75 73 68 20 63 70 64 |/.static| ush cpd|
|00002160| 69 73 74 5b 5d 20 3d 20 | 7b 20 20 20 20 20 20 20 |ist[] = |{ |
|00002170| 20 20 2f 2a 20 43 6f 70 | 79 20 6f 66 66 73 65 74 | /* Cop|y offset|
|00002180| 73 20 66 6f 72 20 64 69 | 73 74 61 6e 63 65 20 63 |s for di|stance c|
|00002190| 6f 64 65 73 20 30 2e 2e | 32 39 20 2a 2f 0d 20 20 |odes 0..|29 */. |
|000021a0| 20 20 20 20 20 20 31 2c | 20 32 2c 20 33 2c 20 34 | 1,| 2, 3, 4|
|000021b0| 2c 20 35 2c 20 37 2c 20 | 39 2c 20 31 33 2c 20 31 |, 5, 7, |9, 13, 1|
|000021c0| 37 2c 20 32 35 2c 20 33 | 33 2c 20 34 39 2c 20 36 |7, 25, 3|3, 49, 6|
|000021d0| 35 2c 20 39 37 2c 20 31 | 32 39 2c 20 31 39 33 2c |5, 97, 1|29, 193,|
|000021e0| 0d 20 20 20 20 20 20 20 | 20 32 35 37 2c 20 33 38 |. | 257, 38|
|000021f0| 35 2c 20 35 31 33 2c 20 | 37 36 39 2c 20 31 30 32 |5, 513, |769, 102|
|00002200| 35 2c 20 31 35 33 37 2c | 20 32 30 34 39 2c 20 33 |5, 1537,| 2049, 3|
|00002210| 30 37 33 2c 20 34 30 39 | 37 2c 20 36 31 34 35 2c |073, 409|7, 6145,|
|00002220| 0d 20 20 20 20 20 20 20 | 20 38 31 39 33 2c 20 31 |. | 8193, 1|
|00002230| 32 32 38 39 2c 20 31 36 | 33 38 35 2c 20 32 34 35 |2289, 16|385, 245|
|00002240| 37 37 7d 3b 0d 73 74 61 | 74 69 63 20 75 73 68 20 |77};.sta|tic ush |
|00002250| 63 70 64 65 78 74 5b 5d | 20 3d 20 7b 20 20 20 20 |cpdext[]| = { |
|00002260| 20 20 20 20 20 2f 2a 20 | 45 78 74 72 61 20 62 69 | /* |Extra bi|
|00002270| 74 73 20 66 6f 72 20 64 | 69 73 74 61 6e 63 65 20 |ts for d|istance |
|00002280| 63 6f 64 65 73 20 2a 2f | 0d 20 20 20 20 20 20 20 |codes */|. |
|00002290| 20 30 2c 20 30 2c 20 30 | 2c 20 30 2c 20 31 2c 20 | 0, 0, 0|, 0, 1, |
|000022a0| 31 2c 20 32 2c 20 32 2c | 20 33 2c 20 33 2c 20 34 |1, 2, 2,| 3, 3, 4|
|000022b0| 2c 20 34 2c 20 35 2c 20 | 35 2c 20 36 2c 20 36 2c |, 4, 5, |5, 6, 6,|
|000022c0| 0d 20 20 20 20 20 20 20 | 20 37 2c 20 37 2c 20 38 |. | 7, 7, 8|
|000022d0| 2c 20 38 2c 20 39 2c 20 | 39 2c 20 31 30 2c 20 31 |, 8, 9, |9, 10, 1|
|000022e0| 30 2c 20 31 31 2c 20 31 | 31 2c 0d 20 20 20 20 20 |0, 11, 1|1,. |
|000022f0| 20 20 20 31 32 2c 20 31 | 32 2c 20 31 33 2c 20 31 | 12, 1|2, 13, 1|
|00002300| 33 7d 3b 0d 0d 0d 0d 2f | 2a 20 4d 61 63 72 6f 73 |3};..../|* Macros|
|00002310| 20 66 6f 72 20 69 6e 66 | 6c 61 74 65 28 29 20 62 | for inf|late() b|
|00002320| 69 74 20 70 65 65 6b 69 | 6e 67 20 61 6e 64 20 67 |it peeki|ng and g|
|00002330| 72 61 62 62 69 6e 67 2e | 0d 20 20 20 54 68 65 20 |rabbing.|. The |
|00002340| 75 73 61 67 65 20 69 73 | 3a 0d 20 20 20 0d 20 20 |usage is|:. . |
|00002350| 20 20 20 20 20 20 4e 45 | 45 44 42 49 54 53 28 6a | NE|EDBITS(j|
|00002360| 29 0d 20 20 20 20 20 20 | 20 20 78 20 3d 20 62 20 |). | x = b |
|00002370| 26 20 6d 61 73 6b 5f 62 | 69 74 73 5b 6a 5d 3b 0d |& mask_b|its[j];.|
|00002380| 20 20 20 20 20 20 20 20 | 44 55 4d 50 42 49 54 53 | |DUMPBITS|
|00002390| 28 6a 29 0d 0d 20 20 20 | 77 68 65 72 65 20 4e 45 |(j).. |where NE|
|000023a0| 45 44 42 49 54 53 20 6d | 61 6b 65 73 20 73 75 72 |EDBITS m|akes sur|
|000023b0| 65 20 74 68 61 74 20 62 | 20 68 61 73 20 61 74 20 |e that b| has at |
|000023c0| 6c 65 61 73 74 20 6a 20 | 62 69 74 73 20 69 6e 20 |least j |bits in |
|000023d0| 69 74 2c 20 61 6e 64 0d | 20 20 20 44 55 4d 50 42 |it, and.| DUMPB|
|000023e0| 49 54 53 20 72 65 6d 6f | 76 65 73 20 74 68 65 20 |ITS remo|ves the |
|000023f0| 62 69 74 73 20 66 72 6f | 6d 20 62 2e 20 20 54 68 |bits fro|m b. Th|
|00002400| 65 20 6d 61 63 72 6f 73 | 20 75 73 65 20 74 68 65 |e macros| use the|
|00002410| 20 76 61 72 69 61 62 6c | 65 20 6b 0d 20 20 20 66 | variabl|e k. f|
|00002420| 6f 72 20 74 68 65 20 6e | 75 6d 62 65 72 20 6f 66 |or the n|umber of|
|00002430| 20 62 69 74 73 20 69 6e | 20 62 2e 20 20 4e 6f 72 | bits in| b. Nor|
|00002440| 6d 61 6c 6c 79 2c 20 62 | 20 61 6e 64 20 6b 20 61 |mally, b| and k a|
|00002450| 72 65 20 72 65 67 69 73 | 74 65 72 0d 20 20 20 76 |re regis|ter. v|
|00002460| 61 72 69 61 62 6c 65 73 | 20 66 6f 72 20 73 70 65 |ariables| for spe|
|00002470| 65 64 2c 20 61 6e 64 20 | 61 72 65 20 69 6e 69 74 |ed, and |are init|
|00002480| 69 61 6c 69 7a 65 64 20 | 61 74 20 74 68 65 20 62 |ialized |at the b|
|00002490| 65 67 69 6e 6e 69 6e 67 | 20 6f 66 20 61 0d 20 20 |eginning| of a. |
|000024a0| 20 72 6f 75 74 69 6e 65 | 20 74 68 61 74 20 75 73 | routine| that us|
|000024b0| 65 73 20 74 68 65 73 65 | 20 6d 61 63 72 6f 73 20 |es these| macros |
|000024c0| 66 72 6f 6d 20 61 20 67 | 6c 6f 62 61 6c 20 62 69 |from a g|lobal bi|
|000024d0| 74 20 62 75 66 66 65 72 | 20 61 6e 64 20 63 6f 75 |t buffer| and cou|
|000024e0| 6e 74 2e 0d 0d 20 20 20 | 49 66 20 77 65 20 61 73 |nt... |If we as|
|000024f0| 73 75 6d 65 20 74 68 61 | 74 20 45 4f 42 20 77 69 |sume tha|t EOB wi|
|00002500| 6c 6c 20 62 65 20 74 68 | 65 20 6c 6f 6e 67 65 73 |ll be th|e longes|
|00002510| 74 20 63 6f 64 65 2c 20 | 74 68 65 6e 20 77 65 20 |t code, |then we |
|00002520| 77 69 6c 6c 20 6e 65 76 | 65 72 0d 20 20 20 61 73 |will nev|er. as|
|00002530| 6b 20 66 6f 72 20 62 69 | 74 73 20 77 69 74 68 20 |k for bi|ts with |
|00002540| 4e 45 45 44 42 49 54 53 | 20 74 68 61 74 20 61 72 |NEEDBITS| that ar|
|00002550| 65 20 62 65 79 6f 6e 64 | 20 74 68 65 20 65 6e 64 |e beyond| the end|
|00002560| 20 6f 66 20 74 68 65 20 | 73 74 72 65 61 6d 2e 0d | of the |stream..|
|00002570| 20 20 20 53 6f 2c 20 4e | 45 45 44 42 49 54 53 20 | So, N|EEDBITS |
|00002580| 73 68 6f 75 6c 64 20 6e | 6f 74 20 72 65 61 64 20 |should n|ot read |
|00002590| 61 6e 79 20 6d 6f 72 65 | 20 62 79 74 65 73 20 74 |any more| bytes t|
|000025a0| 68 61 6e 20 61 72 65 20 | 6e 65 65 64 65 64 20 74 |han are |needed t|
|000025b0| 6f 0d 20 20 20 6d 65 65 | 74 20 74 68 65 20 72 65 |o. mee|t the re|
|000025c0| 71 75 65 73 74 2e 20 20 | 54 68 65 6e 20 6e 6f 20 |quest. |Then no |
|000025d0| 62 79 74 65 73 20 6e 65 | 65 64 20 74 6f 20 62 65 |bytes ne|ed to be|
|000025e0| 20 22 72 65 74 75 72 6e | 65 64 22 20 74 6f 20 74 | "return|ed" to t|
|000025f0| 68 65 20 62 75 66 66 65 | 72 0d 20 20 20 61 74 20 |he buffe|r. at |
|00002600| 74 68 65 20 65 6e 64 20 | 6f 66 20 74 68 65 20 6c |the end |of the l|
|00002610| 61 73 74 20 62 6c 6f 63 | 6b 2e 0d 0d 20 20 20 48 |ast bloc|k... H|
|00002620| 6f 77 65 76 65 72 2c 20 | 74 68 69 73 20 61 73 73 |owever, |this ass|
|00002630| 75 6d 70 74 69 6f 6e 20 | 69 73 20 6e 6f 74 20 74 |umption |is not t|
|00002640| 72 75 65 20 66 6f 72 20 | 66 69 78 65 64 20 62 6c |rue for |fixed bl|
|00002650| 6f 63 6b 73 2d 2d 74 68 | 65 20 45 4f 42 20 63 6f |ocks--th|e EOB co|
|00002660| 64 65 0d 20 20 20 69 73 | 20 37 20 62 69 74 73 2c |de. is| 7 bits,|
|00002670| 20 62 75 74 20 74 68 65 | 20 6f 74 68 65 72 20 6c | but the| other l|
|00002680| 69 74 65 72 61 6c 2f 6c | 65 6e 67 74 68 20 63 6f |iteral/l|ength co|
|00002690| 64 65 73 20 63 61 6e 20 | 62 65 20 38 20 6f 72 20 |des can |be 8 or |
|000026a0| 39 20 62 69 74 73 2e 0d | 20 20 20 28 54 68 65 20 |9 bits..| (The |
|000026b0| 45 4f 42 20 63 6f 64 65 | 20 69 73 20 73 68 6f 72 |EOB code| is shor|
|000026c0| 74 65 72 20 74 68 61 6e | 20 6f 74 68 65 72 20 63 |ter than| other c|
|000026d0| 6f 64 65 73 20 62 65 63 | 61 75 73 65 20 66 69 78 |odes bec|ause fix|
|000026e0| 65 64 20 62 6c 6f 63 6b | 73 20 61 72 65 0d 20 20 |ed block|s are. |
|000026f0| 20 67 65 6e 65 72 61 6c | 6c 79 20 73 68 6f 72 74 | general|ly short|
|00002700| 2e 20 20 53 6f 2c 20 77 | 68 69 6c 65 20 61 20 62 |. So, w|hile a b|
|00002710| 6c 6f 63 6b 20 61 6c 77 | 61 79 73 20 68 61 73 20 |lock alw|ays has |
|00002720| 61 6e 20 45 4f 42 2c 20 | 6d 61 6e 79 20 6f 74 68 |an EOB, |many oth|
|00002730| 65 72 0d 20 20 20 6c 69 | 74 65 72 61 6c 2f 6c 65 |er. li|teral/le|
|00002740| 6e 67 74 68 20 63 6f 64 | 65 73 20 68 61 76 65 20 |ngth cod|es have |
|00002750| 61 20 73 69 67 6e 69 66 | 69 63 61 6e 74 6c 79 20 |a signif|icantly |
|00002760| 6c 6f 77 65 72 20 70 72 | 6f 62 61 62 69 6c 69 74 |lower pr|obabilit|
|00002770| 79 20 6f 66 0d 20 20 20 | 73 68 6f 77 69 6e 67 20 |y of. |showing |
|00002780| 75 70 20 61 74 20 61 6c | 6c 2e 29 20 20 48 6f 77 |up at al|l.) How|
|00002790| 65 76 65 72 2c 20 62 79 | 20 6d 61 6b 69 6e 67 20 |ever, by| making |
|000027a0| 74 68 65 20 66 69 72 73 | 74 20 74 61 62 6c 65 20 |the firs|t table |
|000027b0| 68 61 76 65 20 61 0d 20 | 20 20 6c 6f 6f 6b 75 70 |have a. | lookup|
|000027c0| 20 6f 66 20 73 65 76 65 | 6e 20 62 69 74 73 2c 20 | of seve|n bits, |
|000027d0| 74 68 65 20 45 4f 42 20 | 63 6f 64 65 20 77 69 6c |the EOB |code wil|
|000027e0| 6c 20 62 65 20 66 6f 75 | 6e 64 20 69 6e 20 74 68 |l be fou|nd in th|
|000027f0| 61 74 20 66 69 72 73 74 | 0d 20 20 20 6c 6f 6f 6b |at first|. look|
|00002800| 75 70 2c 20 61 6e 64 20 | 73 6f 20 77 69 6c 6c 20 |up, and |so will |
|00002810| 6e 6f 74 20 72 65 71 75 | 69 72 65 20 74 68 61 74 |not requ|ire that|
|00002820| 20 74 6f 6f 20 6d 61 6e | 79 20 62 69 74 73 20 62 | too man|y bits b|
|00002830| 65 20 70 75 6c 6c 65 64 | 20 66 72 6f 6d 0d 20 20 |e pulled| from. |
|00002840| 20 74 68 65 20 73 74 72 | 65 61 6d 2e 0d 20 2a 2f | the str|eam.. */|
|00002850| 0d 0d 75 6c 67 20 62 62 | 3b 20 20 20 20 20 20 20 |..ulg bb|; |
|00002860| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002870| 20 20 2f 2a 20 62 69 74 | 20 62 75 66 66 65 72 20 | /* bit| buffer |
|00002880| 2a 2f 0d 75 6e 73 69 67 | 6e 65 64 20 62 6b 3b 20 |*/.unsig|ned bk; |
|00002890| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000028a0| 20 20 20 2f 2a 20 62 69 | 74 73 20 69 6e 20 62 69 | /* bi|ts in bi|
|000028b0| 74 20 62 75 66 66 65 72 | 20 2a 2f 0d 0d 75 73 68 |t buffer| */..ush|
|000028c0| 20 6d 61 73 6b 5f 62 69 | 74 73 5b 5d 20 3d 20 7b | mask_bi|ts[] = {|
|000028d0| 0d 20 20 20 20 30 78 30 | 30 30 30 2c 0d 20 20 20 |. 0x0|000,. |
|000028e0| 20 30 78 30 30 30 31 2c | 20 30 78 30 30 30 33 2c | 0x0001,| 0x0003,|
|000028f0| 20 30 78 30 30 30 37 2c | 20 30 78 30 30 30 66 2c | 0x0007,| 0x000f,|
|00002900| 20 30 78 30 30 31 66 2c | 20 30 78 30 30 33 66 2c | 0x001f,| 0x003f,|
|00002910| 20 30 78 30 30 37 66 2c | 20 30 78 30 30 66 66 2c | 0x007f,| 0x00ff,|
|00002920| 0d 20 20 20 20 30 78 30 | 31 66 66 2c 20 30 78 30 |. 0x0|1ff, 0x0|
|00002930| 33 66 66 2c 20 30 78 30 | 37 66 66 2c 20 30 78 30 |3ff, 0x0|7ff, 0x0|
|00002940| 66 66 66 2c 20 30 78 31 | 66 66 66 2c 20 30 78 33 |fff, 0x1|fff, 0x3|
|00002950| 66 66 66 2c 20 30 78 37 | 66 66 66 2c 20 30 78 66 |fff, 0x7|fff, 0xf|
|00002960| 66 66 66 0d 7d 3b 0d 0d | 23 69 66 64 65 66 20 43 |fff.};..|#ifdef C|
|00002970| 52 59 50 54 0d 20 20 75 | 63 68 20 63 63 3b 0d 23 |RYPT. u|ch cc;.#|
|00002980| 20 20 64 65 66 69 6e 65 | 20 4e 45 58 54 42 59 54 | define| NEXTBYT|
|00002990| 45 28 29 20 5c 0d 20 20 | 20 20 20 28 64 65 63 72 |E() \. | (decr|
|000029a0| 79 70 74 20 3f 20 28 63 | 63 20 3d 20 67 65 74 5f |ypt ? (c|c = get_|
|000029b0| 62 79 74 65 28 29 2c 20 | 7a 64 65 63 6f 64 65 28 |byte(), |zdecode(|
|000029c0| 63 63 29 2c 20 63 63 29 | 20 3a 20 67 65 74 5f 62 |cc), cc)| : get_b|
|000029d0| 79 74 65 28 29 29 0d 23 | 65 6c 73 65 0d 23 20 20 |yte()).#|else.# |
|000029e0| 64 65 66 69 6e 65 20 4e | 45 58 54 42 59 54 45 28 |define N|EXTBYTE(|
|000029f0| 29 20 20 28 75 63 68 29 | 67 65 74 5f 62 79 74 65 |) (uch)|get_byte|
|00002a00| 28 29 0d 23 65 6e 64 69 | 66 0d 23 64 65 66 69 6e |().#endi|f.#defin|
|00002a10| 65 20 4e 45 45 44 42 49 | 54 53 28 6e 29 20 7b 77 |e NEEDBI|TS(n) {w|
|00002a20| 68 69 6c 65 28 6b 3c 28 | 6e 29 29 7b 62 7c 3d 28 |hile(k<(|n)){b|=(|
|00002a30| 28 75 6c 67 29 4e 45 58 | 54 42 59 54 45 28 29 29 |(ulg)NEX|TBYTE())|
|00002a40| 3c 3c 6b 3b 6b 2b 3d 38 | 3b 7d 7d 0d 23 64 65 66 |<<k;k+=8|;}}.#def|
|00002a50| 69 6e 65 20 44 55 4d 50 | 42 49 54 53 28 6e 29 20 |ine DUMP|BITS(n) |
|00002a60| 7b 62 3e 3e 3d 28 6e 29 | 3b 6b 2d 3d 28 6e 29 3b |{b>>=(n)|;k-=(n);|
|00002a70| 7d 0d 0d 0d 2f 2a 0d 20 | 20 20 48 75 66 66 6d 61 |}.../*. | Huffma|
|00002a80| 6e 20 63 6f 64 65 20 64 | 65 63 6f 64 69 6e 67 20 |n code d|ecoding |
|00002a90| 69 73 20 70 65 72 66 6f | 72 6d 65 64 20 75 73 69 |is perfo|rmed usi|
|00002aa0| 6e 67 20 61 20 6d 75 6c | 74 69 2d 6c 65 76 65 6c |ng a mul|ti-level|
|00002ab0| 20 74 61 62 6c 65 20 6c | 6f 6f 6b 75 70 2e 0d 20 | table l|ookup.. |
|00002ac0| 20 20 54 68 65 20 66 61 | 73 74 65 73 74 20 77 61 | The fa|stest wa|
|00002ad0| 79 20 74 6f 20 64 65 63 | 6f 64 65 20 69 73 20 74 |y to dec|ode is t|
|00002ae0| 6f 20 73 69 6d 70 6c 79 | 20 62 75 69 6c 64 20 61 |o simply| build a|
|00002af0| 20 6c 6f 6f 6b 75 70 20 | 74 61 62 6c 65 20 77 68 | lookup |table wh|
|00002b00| 6f 73 65 0d 20 20 20 73 | 69 7a 65 20 69 73 20 64 |ose. s|ize is d|
|00002b10| 65 74 65 72 6d 69 6e 65 | 64 20 62 79 20 74 68 65 |etermine|d by the|
|00002b20| 20 6c 6f 6e 67 65 73 74 | 20 63 6f 64 65 2e 20 20 | longest| code. |
|00002b30| 48 6f 77 65 76 65 72 2c | 20 74 68 65 20 74 69 6d |However,| the tim|
|00002b40| 65 20 69 74 20 74 61 6b | 65 73 0d 20 20 20 74 6f |e it tak|es. to|
|00002b50| 20 62 75 69 6c 64 20 74 | 68 69 73 20 74 61 62 6c | build t|his tabl|
|00002b60| 65 20 63 61 6e 20 61 6c | 73 6f 20 62 65 20 61 20 |e can al|so be a |
|00002b70| 66 61 63 74 6f 72 20 69 | 66 20 74 68 65 20 64 61 |factor i|f the da|
|00002b80| 74 61 20 62 65 69 6e 67 | 20 64 65 63 6f 64 65 64 |ta being| decoded|
|00002b90| 0d 20 20 20 69 73 20 6e | 6f 74 20 76 65 72 79 20 |. is n|ot very |
|00002ba0| 6c 6f 6e 67 2e 20 20 54 | 68 65 20 6d 6f 73 74 20 |long. T|he most |
|00002bb0| 63 6f 6d 6d 6f 6e 20 63 | 6f 64 65 73 20 61 72 65 |common c|odes are|
|00002bc0| 20 6e 65 63 65 73 73 61 | 72 69 6c 79 20 74 68 65 | necessa|rily the|
|00002bd0| 0d 20 20 20 73 68 6f 72 | 74 65 73 74 20 63 6f 64 |. shor|test cod|
|00002be0| 65 73 2c 20 73 6f 20 74 | 68 6f 73 65 20 63 6f 64 |es, so t|hose cod|
|00002bf0| 65 73 20 64 6f 6d 69 6e | 61 74 65 20 74 68 65 20 |es domin|ate the |
|00002c00| 64 65 63 6f 64 69 6e 67 | 20 74 69 6d 65 2c 20 61 |decoding| time, a|
|00002c10| 6e 64 20 68 65 6e 63 65 | 0d 20 20 20 74 68 65 20 |nd hence|. the |
|00002c20| 73 70 65 65 64 2e 20 20 | 54 68 65 20 69 64 65 61 |speed. |The idea|
|00002c30| 20 69 73 20 79 6f 75 20 | 63 61 6e 20 68 61 76 65 | is you |can have|
|00002c40| 20 61 20 73 68 6f 72 74 | 65 72 20 74 61 62 6c 65 | a short|er table|
|00002c50| 20 74 68 61 74 20 64 65 | 63 6f 64 65 73 20 74 68 | that de|codes th|
|00002c60| 65 0d 20 20 20 73 68 6f | 72 74 65 72 2c 20 6d 6f |e. sho|rter, mo|
|00002c70| 72 65 20 70 72 6f 62 61 | 62 6c 65 20 63 6f 64 65 |re proba|ble code|
|00002c80| 73 2c 20 61 6e 64 20 74 | 68 65 6e 20 70 6f 69 6e |s, and t|hen poin|
|00002c90| 74 20 74 6f 20 73 75 62 | 73 69 64 69 61 72 79 20 |t to sub|sidiary |
|00002ca0| 74 61 62 6c 65 73 20 66 | 6f 72 0d 20 20 20 74 68 |tables f|or. th|
|00002cb0| 65 20 6c 6f 6e 67 65 72 | 20 63 6f 64 65 73 2e 20 |e longer| codes. |
|00002cc0| 20 54 68 65 20 74 69 6d | 65 20 69 74 20 63 6f 73 | The tim|e it cos|
|00002cd0| 74 73 20 74 6f 20 64 65 | 63 6f 64 65 20 74 68 65 |ts to de|code the|
|00002ce0| 20 6c 6f 6e 67 65 72 20 | 63 6f 64 65 73 20 69 73 | longer |codes is|
|00002cf0| 0d 20 20 20 74 68 65 6e | 20 74 72 61 64 65 64 20 |. then| traded |
|00002d00| 61 67 61 69 6e 73 74 20 | 74 68 65 20 74 69 6d 65 |against |the time|
|00002d10| 20 69 74 20 74 61 6b 65 | 73 20 74 6f 20 6d 61 6b | it take|s to mak|
|00002d20| 65 20 6c 6f 6e 67 65 72 | 20 74 61 62 6c 65 73 2e |e longer| tables.|
|00002d30| 0d 0d 20 20 20 54 68 69 | 73 20 72 65 73 75 6c 74 |.. Thi|s result|
|00002d40| 73 20 6f 66 20 74 68 69 | 73 20 74 72 61 64 65 20 |s of thi|s trade |
|00002d50| 61 72 65 20 69 6e 20 74 | 68 65 20 76 61 72 69 61 |are in t|he varia|
|00002d60| 62 6c 65 73 20 6c 62 69 | 74 73 20 61 6e 64 20 64 |bles lbi|ts and d|
|00002d70| 62 69 74 73 0d 20 20 20 | 62 65 6c 6f 77 2e 20 20 |bits. |below. |
|00002d80| 6c 62 69 74 73 20 69 73 | 20 74 68 65 20 6e 75 6d |lbits is| the num|
|00002d90| 62 65 72 20 6f 66 20 62 | 69 74 73 20 74 68 65 20 |ber of b|its the |
|00002da0| 66 69 72 73 74 20 6c 65 | 76 65 6c 20 74 61 62 6c |first le|vel tabl|
|00002db0| 65 20 66 6f 72 20 6c 69 | 74 65 72 61 6c 2f 0d 20 |e for li|teral/. |
|00002dc0| 20 20 6c 65 6e 67 74 68 | 20 63 6f 64 65 73 20 63 | length| codes c|
|00002dd0| 61 6e 20 64 65 63 6f 64 | 65 20 69 6e 20 6f 6e 65 |an decod|e in one|
|00002de0| 20 73 74 65 70 2c 20 61 | 6e 64 20 64 62 69 74 73 | step, a|nd dbits|
|00002df0| 20 69 73 20 74 68 65 20 | 73 61 6d 65 20 74 68 69 | is the |same thi|
|00002e00| 6e 67 20 66 6f 72 0d 20 | 20 20 74 68 65 20 64 69 |ng for. | the di|
|00002e10| 73 74 61 6e 63 65 20 63 | 6f 64 65 73 2e 20 20 53 |stance c|odes. S|
|00002e20| 75 62 73 65 71 75 65 6e | 74 20 74 61 62 6c 65 73 |ubsequen|t tables|
|00002e30| 20 61 72 65 20 61 6c 73 | 6f 20 6c 65 73 73 20 74 | are als|o less t|
|00002e40| 68 61 6e 20 6f 72 20 65 | 71 75 61 6c 20 74 6f 0d |han or e|qual to.|
|00002e50| 20 20 20 74 68 6f 73 65 | 20 73 69 7a 65 73 2e 20 | those| sizes. |
|00002e60| 20 54 68 65 73 65 20 76 | 61 6c 75 65 73 20 6d 61 | These v|alues ma|
|00002e70| 79 20 62 65 20 61 64 6a | 75 73 74 65 64 20 65 69 |y be adj|usted ei|
|00002e80| 74 68 65 72 20 77 68 65 | 6e 20 61 6c 6c 20 6f 66 |ther whe|n all of|
|00002e90| 20 74 68 65 0d 20 20 20 | 63 6f 64 65 73 20 61 72 | the. |codes ar|
|00002ea0| 65 20 73 68 6f 72 74 65 | 72 20 74 68 61 6e 20 74 |e shorte|r than t|
|00002eb0| 68 61 74 2c 20 69 6e 20 | 77 68 69 63 68 20 63 61 |hat, in |which ca|
|00002ec0| 73 65 20 74 68 65 20 6c | 6f 6e 67 65 73 74 20 63 |se the l|ongest c|
|00002ed0| 6f 64 65 20 6c 65 6e 67 | 74 68 20 69 6e 0d 20 20 |ode leng|th in. |
|00002ee0| 20 62 69 74 73 20 69 73 | 20 75 73 65 64 2c 20 6f | bits is| used, o|
|00002ef0| 72 20 77 68 65 6e 20 74 | 68 65 20 73 68 6f 72 74 |r when t|he short|
|00002f00| 65 73 74 20 63 6f 64 65 | 20 69 73 20 2a 6c 6f 6e |est code| is *lon|
|00002f10| 67 65 72 2a 20 74 68 61 | 6e 20 74 68 65 20 72 65 |ger* tha|n the re|
|00002f20| 71 75 65 73 74 65 64 0d | 20 20 20 74 61 62 6c 65 |quested.| table|
|00002f30| 20 73 69 7a 65 2c 20 69 | 6e 20 77 68 69 63 68 20 | size, i|n which |
|00002f40| 63 61 73 65 20 74 68 65 | 20 6c 65 6e 67 74 68 20 |case the| length |
|00002f50| 6f 66 20 74 68 65 20 73 | 68 6f 72 74 65 73 74 20 |of the s|hortest |
|00002f60| 63 6f 64 65 20 69 6e 20 | 62 69 74 73 20 69 73 0d |code in |bits is.|
|00002f70| 20 20 20 75 73 65 64 2e | 0d 0d 20 20 20 54 68 65 | used.|.. The|
|00002f80| 72 65 20 61 72 65 20 74 | 77 6f 20 64 69 66 66 65 |re are t|wo diffe|
|00002f90| 72 65 6e 74 20 76 61 6c | 75 65 73 20 66 6f 72 20 |rent val|ues for |
|00002fa0| 74 68 65 20 74 77 6f 20 | 74 61 62 6c 65 73 2c 20 |the two |tables, |
|00002fb0| 73 69 6e 63 65 20 74 68 | 65 79 20 63 6f 64 65 20 |since th|ey code |
|00002fc0| 61 0d 20 20 20 64 69 66 | 66 65 72 65 6e 74 20 6e |a. dif|ferent n|
|00002fd0| 75 6d 62 65 72 20 6f 66 | 20 70 6f 73 73 69 62 69 |umber of| possibi|
|00002fe0| 6c 69 74 69 65 73 20 65 | 61 63 68 2e 20 20 54 68 |lities e|ach. Th|
|00002ff0| 65 20 6c 69 74 65 72 61 | 6c 2f 6c 65 6e 67 74 68 |e litera|l/length|
|00003000| 20 74 61 62 6c 65 0d 20 | 20 20 63 6f 64 65 73 20 | table. | codes |
|00003010| 32 38 36 20 70 6f 73 73 | 69 62 6c 65 20 76 61 6c |286 poss|ible val|
|00003020| 75 65 73 2c 20 6f 72 20 | 69 6e 20 61 20 66 6c 61 |ues, or |in a fla|
|00003030| 74 20 63 6f 64 65 2c 20 | 61 20 6c 69 74 74 6c 65 |t code, |a little|
|00003040| 20 6f 76 65 72 20 65 69 | 67 68 74 0d 20 20 20 62 | over ei|ght. b|
|00003050| 69 74 73 2e 20 20 54 68 | 65 20 64 69 73 74 61 6e |its. Th|e distan|
|00003060| 63 65 20 74 61 62 6c 65 | 20 63 6f 64 65 73 20 33 |ce table| codes 3|
|00003070| 30 20 70 6f 73 73 69 62 | 6c 65 20 76 61 6c 75 65 |0 possib|le value|
|00003080| 73 2c 20 6f 72 20 61 20 | 6c 69 74 74 6c 65 20 6c |s, or a |little l|
|00003090| 65 73 73 0d 20 20 20 74 | 68 61 6e 20 66 69 76 65 |ess. t|han five|
|000030a0| 20 62 69 74 73 2c 20 66 | 6c 61 74 2e 20 20 54 68 | bits, f|lat. Th|
|000030b0| 65 20 6f 70 74 69 6d 75 | 6d 20 76 61 6c 75 65 73 |e optimu|m values|
|000030c0| 20 66 6f 72 20 73 70 65 | 65 64 20 65 6e 64 20 75 | for spe|ed end u|
|000030d0| 70 20 62 65 69 6e 67 0d | 20 20 20 61 62 6f 75 74 |p being.| about|
|000030e0| 20 6f 6e 65 20 62 69 74 | 20 6d 6f 72 65 20 74 68 | one bit| more th|
|000030f0| 61 6e 20 74 68 6f 73 65 | 2c 20 73 6f 20 6c 62 69 |an those|, so lbi|
|00003100| 74 73 20 69 73 20 38 2b | 31 20 61 6e 64 20 64 62 |ts is 8+|1 and db|
|00003110| 69 74 73 20 69 73 20 35 | 2b 31 2e 0d 20 20 20 54 |its is 5|+1.. T|
|00003120| 68 65 20 6f 70 74 69 6d | 75 6d 20 76 61 6c 75 65 |he optim|um value|
|00003130| 73 20 6d 61 79 20 64 69 | 66 66 65 72 20 74 68 6f |s may di|ffer tho|
|00003140| 75 67 68 20 66 72 6f 6d | 20 6d 61 63 68 69 6e 65 |ugh from| machine|
|00003150| 20 74 6f 20 6d 61 63 68 | 69 6e 65 2c 20 61 6e 64 | to mach|ine, and|
|00003160| 0d 20 20 20 70 6f 73 73 | 69 62 6c 79 20 65 76 65 |. poss|ibly eve|
|00003170| 6e 20 62 65 74 77 65 65 | 6e 20 63 6f 6d 70 69 6c |n betwee|n compil|
|00003180| 65 72 73 2e 20 20 59 6f | 75 72 20 6d 69 6c 65 61 |ers. Yo|ur milea|
|00003190| 67 65 20 6d 61 79 20 76 | 61 72 79 2e 0d 20 2a 2f |ge may v|ary.. */|
|000031a0| 0d 0d 0d 69 6e 74 20 6c | 62 69 74 73 20 3d 20 39 |...int l|bits = 9|
|000031b0| 3b 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 62 69 |; | /* bi|
|000031c0| 74 73 20 69 6e 20 62 61 | 73 65 20 6c 69 74 65 72 |ts in ba|se liter|
|000031d0| 61 6c 2f 6c 65 6e 67 74 | 68 20 6c 6f 6f 6b 75 70 |al/lengt|h lookup|
|000031e0| 20 74 61 62 6c 65 20 2a | 2f 0d 69 6e 74 20 64 62 | table *|/.int db|
|000031f0| 69 74 73 20 3d 20 36 3b | 20 20 20 20 20 20 20 20 |its = 6;| |
|00003200| 20 20 2f 2a 20 62 69 74 | 73 20 69 6e 20 62 61 73 | /* bit|s in bas|
|00003210| 65 20 64 69 73 74 61 6e | 63 65 20 6c 6f 6f 6b 75 |e distan|ce looku|
|00003220| 70 20 74 61 62 6c 65 20 | 2a 2f 0d 0d 0d 2f 2a 20 |p table |*/.../* |
|00003230| 49 66 20 42 4d 41 58 20 | 6e 65 65 64 73 20 74 6f |If BMAX |needs to|
|00003240| 20 62 65 20 6c 61 72 67 | 65 72 20 74 68 61 6e 20 | be larg|er than |
|00003250| 31 36 2c 20 74 68 65 6e | 20 68 20 61 6e 64 20 78 |16, then| h and x|
|00003260| 5b 5d 20 73 68 6f 75 6c | 64 20 62 65 20 75 6c 67 |[] shoul|d be ulg|
|00003270| 2e 20 2a 2f 0d 23 64 65 | 66 69 6e 65 20 42 4d 41 |. */.#de|fine BMA|
|00003280| 58 20 31 36 20 20 20 20 | 20 20 20 20 20 2f 2a 20 |X 16 | /* |
|00003290| 6d 61 78 69 6d 75 6d 20 | 62 69 74 20 6c 65 6e 67 |maximum |bit leng|
|000032a0| 74 68 20 6f 66 20 61 6e | 79 20 63 6f 64 65 20 28 |th of an|y code (|
|000032b0| 31 36 20 66 6f 72 20 65 | 78 70 6c 6f 64 65 29 20 |16 for e|xplode) |
|000032c0| 2a 2f 0d 23 64 65 66 69 | 6e 65 20 4e 5f 4d 41 58 |*/.#defi|ne N_MAX|
|000032d0| 20 32 38 38 20 20 20 20 | 20 20 20 2f 2a 20 6d 61 | 288 | /* ma|
|000032e0| 78 69 6d 75 6d 20 6e 75 | 6d 62 65 72 20 6f 66 20 |ximum nu|mber of |
|000032f0| 63 6f 64 65 73 20 69 6e | 20 61 6e 79 20 73 65 74 |codes in| any set|
|00003300| 20 2a 2f 0d 0d 0d 75 6e | 73 69 67 6e 65 64 20 68 | */...un|signed h|
|00003310| 75 66 74 73 3b 20 20 20 | 20 20 20 20 20 20 2f 2a |ufts; | /*|
|00003320| 20 74 72 61 63 6b 20 6d | 65 6d 6f 72 79 20 75 73 | track m|emory us|
|00003330| 61 67 65 20 2a 2f 0d 0d | 0d 69 6e 74 20 68 75 66 |age */..|.int huf|
|00003340| 74 5f 62 75 69 6c 64 28 | 62 2c 20 6e 2c 20 73 2c |t_build(|b, n, s,|
|00003350| 20 64 2c 20 65 2c 20 74 | 2c 20 6d 29 0d 75 6e 73 | d, e, t|, m).uns|
|00003360| 69 67 6e 65 64 20 2a 62 | 3b 20 20 20 20 20 20 20 |igned *b|; |
|00003370| 20 20 20 20 20 2f 2a 20 | 63 6f 64 65 20 6c 65 6e | /* |code len|
|00003380| 67 74 68 73 20 69 6e 20 | 62 69 74 73 20 28 61 6c |gths in |bits (al|
|00003390| 6c 20 61 73 73 75 6d 65 | 64 20 3c 3d 20 42 4d 41 |l assume|d <= BMA|
|000033a0| 58 29 20 2a 2f 0d 75 6e | 73 69 67 6e 65 64 20 6e |X) */.un|signed n|
|000033b0| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a |; | /*|
|000033c0| 20 6e 75 6d 62 65 72 20 | 6f 66 20 63 6f 64 65 73 | number |of codes|
|000033d0| 20 28 61 73 73 75 6d 65 | 64 20 3c 3d 20 4e 5f 4d | (assume|d <= N_M|
|000033e0| 41 58 29 20 2a 2f 0d 75 | 6e 73 69 67 6e 65 64 20 |AX) */.u|nsigned |
|000033f0| 73 3b 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f |s; | /|
|00003400| 2a 20 6e 75 6d 62 65 72 | 20 6f 66 20 73 69 6d 70 |* number| of simp|
|00003410| 6c 65 2d 76 61 6c 75 65 | 64 20 63 6f 64 65 73 20 |le-value|d codes |
|00003420| 28 30 2e 2e 73 2d 31 29 | 20 2a 2f 0d 75 73 68 20 |(0..s-1)| */.ush |
|00003430| 2a 64 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |*d; | |
|00003440| 20 20 20 20 2f 2a 20 6c | 69 73 74 20 6f 66 20 62 | /* l|ist of b|
|00003450| 61 73 65 20 76 61 6c 75 | 65 73 20 66 6f 72 20 6e |ase valu|es for n|
|00003460| 6f 6e 2d 73 69 6d 70 6c | 65 20 63 6f 64 65 73 20 |on-simpl|e codes |
|00003470| 2a 2f 0d 75 73 68 20 2a | 65 3b 20 20 20 20 20 20 |*/.ush *|e; |
|00003480| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 6c 69 | | /* li|
|00003490| 73 74 20 6f 66 20 65 78 | 74 72 61 20 62 69 74 73 |st of ex|tra bits|
|000034a0| 20 66 6f 72 20 6e 6f 6e | 2d 73 69 6d 70 6c 65 20 | for non|-simple |
|000034b0| 63 6f 64 65 73 20 2a 2f | 0d 73 74 72 75 63 74 20 |codes */|.struct |
|000034c0| 68 75 66 74 20 2a 2a 74 | 3b 20 20 20 20 20 20 20 |huft **t|; |
|000034d0| 20 2f 2a 20 72 65 73 75 | 6c 74 3a 20 73 74 61 72 | /* resu|lt: star|
|000034e0| 74 69 6e 67 20 74 61 62 | 6c 65 20 2a 2f 0d 69 6e |ting tab|le */.in|
|000034f0| 74 20 2a 6d 3b 20 20 20 | 20 20 20 20 20 20 20 20 |t *m; | |
|00003500| 20 20 20 20 20 20 2f 2a | 20 6d 61 78 69 6d 75 6d | /*| maximum|
|00003510| 20 6c 6f 6f 6b 75 70 20 | 62 69 74 73 2c 20 72 65 | lookup |bits, re|
|00003520| 74 75 72 6e 73 20 61 63 | 74 75 61 6c 20 2a 2f 0d |turns ac|tual */.|
|00003530| 2f 2a 20 47 69 76 65 6e | 20 61 20 6c 69 73 74 20 |/* Given| a list |
|00003540| 6f 66 20 63 6f 64 65 20 | 6c 65 6e 67 74 68 73 20 |of code |lengths |
|00003550| 61 6e 64 20 61 20 6d 61 | 78 69 6d 75 6d 20 74 61 |and a ma|ximum ta|
|00003560| 62 6c 65 20 73 69 7a 65 | 2c 20 6d 61 6b 65 20 61 |ble size|, make a|
|00003570| 20 73 65 74 20 6f 66 0d | 20 20 20 74 61 62 6c 65 | set of.| table|
|00003580| 73 20 74 6f 20 64 65 63 | 6f 64 65 20 74 68 61 74 |s to dec|ode that|
|00003590| 20 73 65 74 20 6f 66 20 | 63 6f 64 65 73 2e 20 20 | set of |codes. |
|000035a0| 52 65 74 75 72 6e 20 7a | 65 72 6f 20 6f 6e 20 73 |Return z|ero on s|
|000035b0| 75 63 63 65 73 73 2c 20 | 6f 6e 65 20 69 66 0d 20 |uccess, |one if. |
|000035c0| 20 20 74 68 65 20 67 69 | 76 65 6e 20 63 6f 64 65 | the gi|ven code|
|000035d0| 20 73 65 74 20 69 73 20 | 69 6e 63 6f 6d 70 6c 65 | set is |incomple|
|000035e0| 74 65 20 28 74 68 65 20 | 74 61 62 6c 65 73 20 61 |te (the |tables a|
|000035f0| 72 65 20 73 74 69 6c 6c | 20 62 75 69 6c 74 20 69 |re still| built i|
|00003600| 6e 20 74 68 69 73 0d 20 | 20 20 63 61 73 65 29 2c |n this. | case),|
|00003610| 20 74 77 6f 20 69 66 20 | 74 68 65 20 69 6e 70 75 | two if |the inpu|
|00003620| 74 20 69 73 20 69 6e 76 | 61 6c 69 64 20 28 61 6c |t is inv|alid (al|
|00003630| 6c 20 7a 65 72 6f 20 6c | 65 6e 67 74 68 20 63 6f |l zero l|ength co|
|00003640| 64 65 73 20 6f 72 20 61 | 6e 0d 20 20 20 6f 76 65 |des or a|n. ove|
|00003650| 72 73 75 62 73 63 72 69 | 62 65 64 20 73 65 74 20 |rsubscri|bed set |
|00003660| 6f 66 20 6c 65 6e 67 74 | 68 73 29 2c 20 61 6e 64 |of lengt|hs), and|
|00003670| 20 74 68 72 65 65 20 69 | 66 20 6e 6f 74 20 65 6e | three i|f not en|
|00003680| 6f 75 67 68 20 6d 65 6d | 6f 72 79 2e 20 2a 2f 0d |ough mem|ory. */.|
|00003690| 7b 0d 20 20 75 6e 73 69 | 67 6e 65 64 20 61 3b 20 |{. unsi|gned a; |
|000036a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000036b0| 20 20 2f 2a 20 63 6f 75 | 6e 74 65 72 20 66 6f 72 | /* cou|nter for|
|000036c0| 20 63 6f 64 65 73 20 6f | 66 20 6c 65 6e 67 74 68 | codes o|f length|
|000036d0| 20 6b 20 2a 2f 0d 20 20 | 75 6e 73 69 67 6e 65 64 | k */. |unsigned|
|000036e0| 20 63 5b 42 4d 41 58 2b | 31 5d 3b 20 20 20 20 20 | c[BMAX+|1]; |
|000036f0| 20 20 20 20 20 20 2f 2a | 20 62 69 74 20 6c 65 6e | /*| bit len|
|00003700| 67 74 68 20 63 6f 75 6e | 74 20 74 61 62 6c 65 20 |gth coun|t table |
|00003710| 2a 2f 0d 20 20 75 6e 73 | 69 67 6e 65 64 20 66 3b |*/. uns|igned f;|
|00003720| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003730| 20 20 20 2f 2a 20 69 20 | 72 65 70 65 61 74 73 20 | /* i |repeats |
|00003740| 69 6e 20 74 61 62 6c 65 | 20 65 76 65 72 79 20 66 |in table| every f|
|00003750| 20 65 6e 74 72 69 65 73 | 20 2a 2f 0d 20 20 69 6e | entries| */. in|
|00003760| 74 20 67 3b 20 20 20 20 | 20 20 20 20 20 20 20 20 |t g; | |
|00003770| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 6d | | /* m|
|00003780| 61 78 69 6d 75 6d 20 63 | 6f 64 65 20 6c 65 6e 67 |aximum c|ode leng|
|00003790| 74 68 20 2a 2f 0d 20 20 | 69 6e 74 20 68 3b 20 20 |th */. |int h; |
|000037a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000037b0| 20 20 20 20 20 20 2f 2a | 20 74 61 62 6c 65 20 6c | /*| table l|
|000037c0| 65 76 65 6c 20 2a 2f 0d | 20 20 72 65 67 69 73 74 |evel */.| regist|
|000037d0| 65 72 20 75 6e 73 69 67 | 6e 65 64 20 69 3b 20 20 |er unsig|ned i; |
|000037e0| 20 20 20 20 20 20 20 20 | 2f 2a 20 63 6f 75 6e 74 | |/* count|
|000037f0| 65 72 2c 20 63 75 72 72 | 65 6e 74 20 63 6f 64 65 |er, curr|ent code|
|00003800| 20 2a 2f 0d 20 20 72 65 | 67 69 73 74 65 72 20 75 | */. re|gister u|
|00003810| 6e 73 69 67 6e 65 64 20 | 6a 3b 20 20 20 20 20 20 |nsigned |j; |
|00003820| 20 20 20 20 2f 2a 20 63 | 6f 75 6e 74 65 72 20 2a | /* c|ounter *|
|00003830| 2f 0d 20 20 72 65 67 69 | 73 74 65 72 20 69 6e 74 |/. regi|ster int|
|00003840| 20 6b 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | k; | |
|00003850| 20 20 2f 2a 20 6e 75 6d | 62 65 72 20 6f 66 20 62 | /* num|ber of b|
|00003860| 69 74 73 20 69 6e 20 63 | 75 72 72 65 6e 74 20 63 |its in c|urrent c|
|00003870| 6f 64 65 20 2a 2f 0d 20 | 20 69 6e 74 20 6c 3b 20 |ode */. | int l; |
|00003880| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003890| 20 20 20 20 20 20 20 2f | 2a 20 62 69 74 73 20 70 | /|* bits p|
|000038a0| 65 72 20 74 61 62 6c 65 | 20 28 72 65 74 75 72 6e |er table| (return|
|000038b0| 65 64 20 69 6e 20 6d 29 | 20 2a 2f 0d 20 20 72 65 |ed in m)| */. re|
|000038c0| 67 69 73 74 65 72 20 75 | 6e 73 69 67 6e 65 64 20 |gister u|nsigned |
|000038d0| 2a 70 3b 20 20 20 20 20 | 20 20 20 20 2f 2a 20 70 |*p; | /* p|
|000038e0| 6f 69 6e 74 65 72 20 69 | 6e 74 6f 20 63 5b 5d 2c |ointer i|nto c[],|
|000038f0| 20 62 5b 5d 2c 20 6f 72 | 20 76 5b 5d 20 2a 2f 0d | b[], or| v[] */.|
|00003900| 20 20 72 65 67 69 73 74 | 65 72 20 73 74 72 75 63 | regist|er struc|
|00003910| 74 20 68 75 66 74 20 2a | 71 3b 20 20 20 20 20 20 |t huft *|q; |
|00003920| 2f 2a 20 70 6f 69 6e 74 | 73 20 74 6f 20 63 75 72 |/* point|s to cur|
|00003930| 72 65 6e 74 20 74 61 62 | 6c 65 20 2a 2f 0d 20 20 |rent tab|le */. |
|00003940| 73 74 72 75 63 74 20 68 | 75 66 74 20 72 3b 20 20 |struct h|uft r; |
|00003950| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a | | /*|
|00003960| 20 74 61 62 6c 65 20 65 | 6e 74 72 79 20 66 6f 72 | table e|ntry for|
|00003970| 20 73 74 72 75 63 74 75 | 72 65 20 61 73 73 69 67 | structu|re assig|
|00003980| 6e 6d 65 6e 74 20 2a 2f | 0d 20 20 73 74 72 75 63 |nment */|. struc|
|00003990| 74 20 68 75 66 74 20 2a | 75 5b 42 4d 41 58 5d 3b |t huft *|u[BMAX];|
|000039a0| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 74 61 62 6c | | /* tabl|
|000039b0| 65 20 73 74 61 63 6b 20 | 2a 2f 0d 20 20 75 6e 73 |e stack |*/. uns|
|000039c0| 69 67 6e 65 64 20 76 5b | 4e 5f 4d 41 58 5d 3b 20 |igned v[|N_MAX]; |
|000039d0| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 76 61 | | /* va|
|000039e0| 6c 75 65 73 20 69 6e 20 | 6f 72 64 65 72 20 6f 66 |lues in |order of|
|000039f0| 20 62 69 74 20 6c 65 6e | 67 74 68 20 2a 2f 0d 20 | bit len|gth */. |
|00003a00| 20 72 65 67 69 73 74 65 | 72 20 69 6e 74 20 77 3b | registe|r int w;|
|00003a10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f | | /|
|00003a20| 2a 20 62 69 74 73 20 62 | 65 66 6f 72 65 20 74 68 |* bits b|efore th|
|00003a30| 69 73 20 74 61 62 6c 65 | 20 3d 3d 20 28 6c 20 2a |is table| == (l *|
|00003a40| 20 68 29 20 2a 2f 0d 20 | 20 75 6e 73 69 67 6e 65 | h) */. | unsigne|
|00003a50| 64 20 78 5b 42 4d 41 58 | 2b 31 5d 3b 20 20 20 20 |d x[BMAX|+1]; |
|00003a60| 20 20 20 20 20 20 20 2f | 2a 20 62 69 74 20 6f 66 | /|* bit of|
|00003a70| 66 73 65 74 73 2c 20 74 | 68 65 6e 20 63 6f 64 65 |fsets, t|hen code|
|00003a80| 20 73 74 61 63 6b 20 2a | 2f 0d 20 20 75 6e 73 69 | stack *|/. unsi|
|00003a90| 67 6e 65 64 20 2a 78 70 | 3b 20 20 20 20 20 20 20 |gned *xp|; |
|00003aa0| 20 20 20 20 20 20 20 20 | 20 20 2f 2a 20 70 6f 69 | | /* poi|
|00003ab0| 6e 74 65 72 20 69 6e 74 | 6f 20 78 20 2a 2f 0d 20 |nter int|o x */. |
|00003ac0| 20 69 6e 74 20 79 3b 20 | 20 20 20 20 20 20 20 20 | int y; | |
|00003ad0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f | | /|
|00003ae0| 2a 20 6e 75 6d 62 65 72 | 20 6f 66 20 64 75 6d 6d |* number| of dumm|
|00003af0| 79 20 63 6f 64 65 73 20 | 61 64 64 65 64 20 2a 2f |y codes |added */|
|00003b00| 0d 20 20 75 6e 73 69 67 | 6e 65 64 20 7a 3b 20 20 |. unsig|ned z; |
|00003b10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003b20| 20 2f 2a 20 6e 75 6d 62 | 65 72 20 6f 66 20 65 6e | /* numb|er of en|
|00003b30| 74 72 69 65 73 20 69 6e | 20 63 75 72 72 65 6e 74 |tries in| current|
|00003b40| 20 74 61 62 6c 65 20 2a | 2f 0d 0d 0d 20 20 2f 2a | table *|/... /*|
|00003b50| 20 47 65 6e 65 72 61 74 | 65 20 63 6f 75 6e 74 73 | Generat|e counts|
|00003b60| 20 66 6f 72 20 65 61 63 | 68 20 62 69 74 20 6c 65 | for eac|h bit le|
|00003b70| 6e 67 74 68 20 2a 2f 0d | 20 20 6d 65 6d 7a 65 72 |ngth */.| memzer|
|00003b80| 6f 28 63 2c 20 73 69 7a | 65 6f 66 28 63 29 29 3b |o(c, siz|eof(c));|
|00003b90| 0d 20 20 70 20 3d 20 62 | 3b 20 20 69 20 3d 20 6e |. p = b|; i = n|
|00003ba0| 3b 0d 20 20 64 6f 20 7b | 0d 20 20 20 20 54 72 61 |;. do {|. Tra|
|00003bb0| 63 65 63 76 28 2a 70 2c | 20 28 73 74 64 65 72 72 |cecv(*p,| (stderr|
|00003bc0| 2c 20 28 6e 2d 69 20 3e | 3d 20 27 20 27 20 26 26 |, (n-i >|= ' ' &&|
|00003bd0| 20 6e 2d 69 20 3c 3d 20 | 27 7e 27 20 3f 20 22 25 | n-i <= |'~' ? "%|
|00003be0| 63 20 25 64 5c 6e 22 20 | 3a 20 22 30 78 25 78 20 |c %d\n" |: "0x%x |
|00003bf0| 25 64 5c 6e 22 29 2c 20 | 0d 09 20 20 20 20 6e 2d |%d\n"), |.. n-|
|00003c00| 69 2c 20 2a 70 29 29 3b | 0d 20 20 20 20 63 5b 2a |i, *p));|. c[*|
|00003c10| 70 5d 2b 2b 3b 20 20 20 | 20 20 20 20 20 20 20 20 |p]++; | |
|00003c20| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 61 73 73 75 | | /* assu|
|00003c30| 6d 65 20 61 6c 6c 20 65 | 6e 74 72 69 65 73 20 3c |me all e|ntries <|
|00003c40| 3d 20 42 4d 41 58 20 2a | 2f 0d 20 20 20 20 70 2b |= BMAX *|/. p+|
|00003c50| 2b 3b 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |+; | |
|00003c60| 20 20 20 20 20 20 20 20 | 2f 2a 20 43 61 6e 27 74 | |/* Can't|
|00003c70| 20 63 6f 6d 62 69 6e 65 | 20 77 69 74 68 20 61 62 | combine| with ab|
|00003c80| 6f 76 65 20 6c 69 6e 65 | 20 28 53 6f 6c 61 72 69 |ove line| (Solari|
|00003c90| 73 20 62 75 67 29 20 2a | 2f 0d 20 20 7d 20 77 68 |s bug) *|/. } wh|
|00003ca0| 69 6c 65 20 28 2d 2d 69 | 29 3b 0d 20 20 69 66 20 |ile (--i|);. if |
|00003cb0| 28 63 5b 30 5d 20 3d 3d | 20 6e 29 20 20 20 20 20 |(c[0] ==| n) |
|00003cc0| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 6e 75 | | /* nu|
|00003cd0| 6c 6c 20 69 6e 70 75 74 | 2d 2d 61 6c 6c 20 7a 65 |ll input|--all ze|
|00003ce0| 72 6f 20 6c 65 6e 67 74 | 68 20 63 6f 64 65 73 20 |ro lengt|h codes |
|00003cf0| 2a 2f 0d 20 20 7b 0d 20 | 20 20 20 2a 74 20 3d 20 |*/. {. | *t = |
|00003d00| 28 73 74 72 75 63 74 20 | 68 75 66 74 20 2a 29 4e |(struct |huft *)N|
|00003d10| 55 4c 4c 3b 0d 20 20 20 | 20 2a 6d 20 3d 20 30 3b |ULL;. | *m = 0;|
|00003d20| 0d 20 20 20 20 72 65 74 | 75 72 6e 20 30 3b 0d 20 |. ret|urn 0;. |
|00003d30| 20 7d 0d 0d 0d 20 20 2f | 2a 20 46 69 6e 64 20 6d | }... /|* Find m|
|00003d40| 69 6e 69 6d 75 6d 20 61 | 6e 64 20 6d 61 78 69 6d |inimum a|nd maxim|
|00003d50| 75 6d 20 6c 65 6e 67 74 | 68 2c 20 62 6f 75 6e 64 |um lengt|h, bound|
|00003d60| 20 2a 6d 20 62 79 20 74 | 68 6f 73 65 20 2a 2f 0d | *m by t|hose */.|
|00003d70| 20 20 6c 20 3d 20 2a 6d | 3b 0d 20 20 66 6f 72 20 | l = *m|;. for |
|00003d80| 28 6a 20 3d 20 31 3b 20 | 6a 20 3c 3d 20 42 4d 41 |(j = 1; |j <= BMA|
|00003d90| 58 3b 20 6a 2b 2b 29 0d | 20 20 20 20 69 66 20 28 |X; j++).| if (|
|00003da0| 63 5b 6a 5d 29 0d 20 20 | 20 20 20 20 62 72 65 61 |c[j]). | brea|
|00003db0| 6b 3b 0d 20 20 6b 20 3d | 20 6a 3b 20 20 20 20 20 |k;. k =| j; |
|00003dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003dd0| 20 20 20 2f 2a 20 6d 69 | 6e 69 6d 75 6d 20 63 6f | /* mi|nimum co|
|00003de0| 64 65 20 6c 65 6e 67 74 | 68 20 2a 2f 0d 20 20 69 |de lengt|h */. i|
|00003df0| 66 20 28 28 75 6e 73 69 | 67 6e 65 64 29 6c 20 3c |f ((unsi|gned)l <|
|00003e00| 20 6a 29 0d 20 20 20 20 | 6c 20 3d 20 6a 3b 0d 20 | j). |l = j;. |
|00003e10| 20 66 6f 72 20 28 69 20 | 3d 20 42 4d 41 58 3b 20 | for (i |= BMAX; |
|00003e20| 69 3b 20 69 2d 2d 29 0d | 20 20 20 20 69 66 20 28 |i; i--).| if (|
|00003e30| 63 5b 69 5d 29 0d 20 20 | 20 20 20 20 62 72 65 61 |c[i]). | brea|
|00003e40| 6b 3b 0d 20 20 67 20 3d | 20 69 3b 20 20 20 20 20 |k;. g =| i; |
|00003e50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003e60| 20 20 20 2f 2a 20 6d 61 | 78 69 6d 75 6d 20 63 6f | /* ma|ximum co|
|00003e70| 64 65 20 6c 65 6e 67 74 | 68 20 2a 2f 0d 20 20 69 |de lengt|h */. i|
|00003e80| 66 20 28 28 75 6e 73 69 | 67 6e 65 64 29 6c 20 3e |f ((unsi|gned)l >|
|00003e90| 20 69 29 0d 20 20 20 20 | 6c 20 3d 20 69 3b 0d 20 | i). |l = i;. |
|00003ea0| 20 2a 6d 20 3d 20 6c 3b | 0d 0d 0d 20 20 2f 2a 20 | *m = l;|... /* |
|00003eb0| 41 64 6a 75 73 74 20 6c | 61 73 74 20 6c 65 6e 67 |Adjust l|ast leng|
|00003ec0| 74 68 20 63 6f 75 6e 74 | 20 74 6f 20 66 69 6c 6c |th count| to fill|
|00003ed0| 20 6f 75 74 20 63 6f 64 | 65 73 2c 20 69 66 20 6e | out cod|es, if n|
|00003ee0| 65 65 64 65 64 20 2a 2f | 0d 20 20 66 6f 72 20 28 |eeded */|. for (|
|00003ef0| 79 20 3d 20 31 20 3c 3c | 20 6a 3b 20 6a 20 3c 20 |y = 1 <<| j; j < |
|00003f00| 69 3b 20 6a 2b 2b 2c 20 | 79 20 3c 3c 3d 20 31 29 |i; j++, |y <<= 1)|
|00003f10| 0d 20 20 20 20 69 66 20 | 28 28 79 20 2d 3d 20 63 |. if |((y -= c|
|00003f20| 5b 6a 5d 29 20 3c 20 30 | 29 0d 20 20 20 20 20 20 |[j]) < 0|). |
|00003f30| 72 65 74 75 72 6e 20 32 | 3b 20 20 20 20 20 20 20 |return 2|; |
|00003f40| 20 20 20 20 20 20 20 20 | 20 20 2f 2a 20 62 61 64 | | /* bad|
|00003f50| 20 69 6e 70 75 74 3a 20 | 6d 6f 72 65 20 63 6f 64 | input: |more cod|
|00003f60| 65 73 20 74 68 61 6e 20 | 62 69 74 73 20 2a 2f 0d |es than |bits */.|
|00003f70| 20 20 69 66 20 28 28 79 | 20 2d 3d 20 63 5b 69 5d | if ((y| -= c[i]|
|00003f80| 29 20 3c 20 30 29 0d 20 | 20 20 20 72 65 74 75 72 |) < 0). | retur|
|00003f90| 6e 20 32 3b 0d 20 20 63 | 5b 69 5d 20 2b 3d 20 79 |n 2;. c|[i] += y|
|00003fa0| 3b 0d 0d 0d 20 20 2f 2a | 20 47 65 6e 65 72 61 74 |;... /*| Generat|
|00003fb0| 65 20 73 74 61 72 74 69 | 6e 67 20 6f 66 66 73 65 |e starti|ng offse|
|00003fc0| 74 73 20 69 6e 74 6f 20 | 74 68 65 20 76 61 6c 75 |ts into |the valu|
|00003fd0| 65 20 74 61 62 6c 65 20 | 66 6f 72 20 65 61 63 68 |e table |for each|
|00003fe0| 20 6c 65 6e 67 74 68 20 | 2a 2f 0d 20 20 78 5b 31 | length |*/. x[1|
|00003ff0| 5d 20 3d 20 6a 20 3d 20 | 30 3b 0d 20 20 70 20 3d |] = j = |0;. p =|
|00004000| 20 63 20 2b 20 31 3b 20 | 20 78 70 20 3d 20 78 20 | c + 1; | xp = x |
|00004010| 2b 20 32 3b 0d 20 20 77 | 68 69 6c 65 20 28 2d 2d |+ 2;. w|hile (--|
|00004020| 69 29 20 7b 20 20 20 20 | 20 20 20 20 20 20 20 20 |i) { | |
|00004030| 20 20 20 20 20 2f 2a 20 | 6e 6f 74 65 20 74 68 61 | /* |note tha|
|00004040| 74 20 69 20 3d 3d 20 67 | 20 66 72 6f 6d 20 61 62 |t i == g| from ab|
|00004050| 6f 76 65 20 2a 2f 0d 20 | 20 20 20 2a 78 70 2b 2b |ove */. | *xp++|
|00004060| 20 3d 20 28 6a 20 2b 3d | 20 2a 70 2b 2b 29 3b 0d | = (j +=| *p++);.|
|00004070| 20 20 7d 0d 0d 0d 20 20 | 2f 2a 20 4d 61 6b 65 20 | }... |/* Make |
|00004080| 61 20 74 61 62 6c 65 20 | 6f 66 20 76 61 6c 75 65 |a table |of value|
|00004090| 73 20 69 6e 20 6f 72 64 | 65 72 20 6f 66 20 62 69 |s in ord|er of bi|
|000040a0| 74 20 6c 65 6e 67 74 68 | 73 20 2a 2f 0d 20 20 70 |t length|s */. p|
|000040b0| 20 3d 20 62 3b 20 20 69 | 20 3d 20 30 3b 0d 20 20 | = b; i| = 0;. |
|000040c0| 64 6f 20 7b 0d 20 20 20 | 20 69 66 20 28 28 6a 20 |do {. | if ((j |
|000040d0| 3d 20 2a 70 2b 2b 29 20 | 21 3d 20 30 29 0d 20 20 |= *p++) |!= 0). |
|000040e0| 20 20 20 20 76 5b 78 5b | 6a 5d 2b 2b 5d 20 3d 20 | v[x[|j]++] = |
|000040f0| 69 3b 0d 20 20 7d 20 77 | 68 69 6c 65 20 28 2b 2b |i;. } w|hile (++|
|00004100| 69 20 3c 20 6e 29 3b 0d | 0d 0d 20 20 2f 2a 20 47 |i < n);.|.. /* G|
|00004110| 65 6e 65 72 61 74 65 20 | 74 68 65 20 48 75 66 66 |enerate |the Huff|
|00004120| 6d 61 6e 20 63 6f 64 65 | 73 20 61 6e 64 20 66 6f |man code|s and fo|
|00004130| 72 20 65 61 63 68 2c 20 | 6d 61 6b 65 20 74 68 65 |r each, |make the|
|00004140| 20 74 61 62 6c 65 20 65 | 6e 74 72 69 65 73 20 2a | table e|ntries *|
|00004150| 2f 0d 20 20 78 5b 30 5d | 20 3d 20 69 20 3d 20 30 |/. x[0]| = i = 0|
|00004160| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |; | |
|00004170| 20 20 2f 2a 20 66 69 72 | 73 74 20 48 75 66 66 6d | /* fir|st Huffm|
|00004180| 61 6e 20 63 6f 64 65 20 | 69 73 20 7a 65 72 6f 20 |an code |is zero |
|00004190| 2a 2f 0d 20 20 70 20 3d | 20 76 3b 20 20 20 20 20 |*/. p =| v; |
|000041a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000041b0| 20 20 20 2f 2a 20 67 72 | 61 62 20 76 61 6c 75 65 | /* gr|ab value|
|000041c0| 73 20 69 6e 20 62 69 74 | 20 6f 72 64 65 72 20 2a |s in bit| order *|
|000041d0| 2f 0d 20 20 68 20 3d 20 | 2d 31 3b 20 20 20 20 20 |/. h = |-1; |
|000041e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000041f0| 20 20 2f 2a 20 6e 6f 20 | 74 61 62 6c 65 73 20 79 | /* no |tables y|
|00004200| 65 74 2d 2d 6c 65 76 65 | 6c 20 2d 31 20 2a 2f 0d |et--leve|l -1 */.|
|00004210| 20 20 77 20 3d 20 2d 6c | 3b 20 20 20 20 20 20 20 | w = -l|; |
|00004220| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004230| 2f 2a 20 62 69 74 73 20 | 64 65 63 6f 64 65 64 20 |/* bits |decoded |
|00004240| 3d 3d 20 28 6c 20 2a 20 | 68 29 20 2a 2f 0d 20 20 |== (l * |h) */. |
|00004250| 75 5b 30 5d 20 3d 20 28 | 73 74 72 75 63 74 20 68 |u[0] = (|struct h|
|00004260| 75 66 74 20 2a 29 4e 55 | 4c 4c 3b 20 20 20 2f 2a |uft *)NU|LL; /*|
|00004270| 20 6a 75 73 74 20 74 6f | 20 6b 65 65 70 20 63 6f | just to| keep co|
|00004280| 6d 70 69 6c 65 72 73 20 | 68 61 70 70 79 20 2a 2f |mpilers |happy */|
|00004290| 0d 20 20 71 20 3d 20 28 | 73 74 72 75 63 74 20 68 |. q = (|struct h|
|000042a0| 75 66 74 20 2a 29 4e 55 | 4c 4c 3b 20 20 20 20 20 |uft *)NU|LL; |
|000042b0| 20 2f 2a 20 64 69 74 74 | 6f 20 2a 2f 0d 20 20 7a | /* ditt|o */. z|
|000042c0| 20 3d 20 30 3b 20 20 20 | 20 20 20 20 20 20 20 20 | = 0; | |
|000042d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 2f 2a 20 | | /* |
|000042e0| 64 69 74 74 6f 20 2a 2f | 0d 0d 20 20 2f 2a 20 67 |ditto */|.. /* g|
|000042f0| 6f 20 74 68 72 6f 75 67 | 68 20 74 68 65 20 62 69 |o throug|h the bi|
|00004300| 74 20 6c 65 6e 67 74 68 | 73 20 28 6b 20 61 6c 72 |t length|s (k alr|
|00004310| 65 61 64 79 20 69 73 20 | 62 69 74 73 20 69 6e 20 |eady is |bits in |
|00004320| 73 68 6f 72 74 65 73 74 | 20 63 6f 64 65 29 20 2a |shortest| code) *|
|00004330| 2f 0d 20 20 66 6f 72 20 | 28 3b 20 6b 20 3c 3d 20 |/. for |(; k <= |
|00004340| 67 3b 20 6b 2b 2b 29 0d | 20 20 7b 0d 20 20 20 20 |g; k++).| {. |
|00004350| 61 20 3d 20 63 5b 6b 5d | 3b 0d 20 20 20 20 77 68 |a = c[k]|;. wh|
|00004360| 69 6c 65 20 28 61 2d 2d | 29 0d 20 20 20 20 7b 0d |ile (a--|). {.|
|00004370| 20 20 20 20 20 20 2f 2a | 20 68 65 72 65 20 69 20 | /*| here i |
|00004380| 69 73 20 74 68 65 20 48 | 75 66 66 6d 61 6e 20 63 |is the H|uffman c|
|00004390| 6f 64 65 20 6f 66 20 6c | 65 6e 67 74 68 20 6b 20 |ode of l|ength k |
|000043a0| 62 69 74 73 20 66 6f 72 | 20 76 61 6c 75 65 20 2a |bits for| value *|
|000043b0| 70 20 2a 2f 0d 20 20 20 | 20 20 20 2f 2a 20 6d 61 |p */. | /* ma|
|000043c0| 6b 65 20 74 61 62 6c 65 | 73 20 75 70 20 74 6f 20 |ke table|s up to |
|000043d0| 72 65 71 75 69 72 65 64 | 20 6c 65 76 65 6c 20 2a |required| level *|
|000043e0| 2f 0d 20 20 20 20 20 20 | 77 68 69 6c 65 20 28 6b |/. |while (k|
|000043f0| 20 3e 20 77 20 2b 20 6c | 29 0d 20 20 20 20 20 20 | > w + l|). |
|00004400| 7b 0d 20 20 20 20 20 20 | 20 20 68 2b 2b 3b 0d 20 |{. | h++;. |
|00004410| 20 20 20 20 20 20 20 77 | 20 2b 3d 20 6c 3b 20 20 | w| += l; |
|00004420| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 2f | | /|
|00004430| 2a 20 70 72 65 76 69 6f | 75 73 20 74 61 62 6c 65 |* previo|us table|
|00004440| 20 61 6c 77 61 79 73 20 | 6c 20 62 69 74 73 20 2a | always |l bits *|
|00004450| 2f 0d 0d 20 20 20 20 20 | 20 20 20 2f 2a 20 63 6f |/.. | /* co|
|00004460| 6d 70 75 74 65 20 6d 69 | 6e 69 6d 75 6d 20 73 69 |mpute mi|nimum si|
|00004470| 7a 65 20 74 61 62 6c 65 | 20 6c 65 73 73 20 74 68 |ze table| less th|
|00004480| 61 6e 20 6f 72 20 65 71 | 75 61 6c 20 74 6f 20 6c |an or eq|ual to l|
|00004490| 20 62 69 74 73 20 2a 2f | 0d 20 20 20 20 20 20 20 | bits */|. |
|000044a0| 20 7a 20 3d 20 28 7a 20 | 3d 20 67 20 2d 20 77 29 | z = (z |= g - w)|
|000044b0| 20 3e 20 28 75 6e 73 69 | 67 6e 65 64 29 6c 20 3f | > (unsi|gned)l ?|
|000044c0| 20 6c 20 3a 20 7a 3b 20 | 20 2f 2a 20 75 70 70 65 | l : z; | /* uppe|
|000044d0| 72 20 6c 69 6d 69 74 20 | 6f 6e 20 74 61 62 6c 65 |r limit |on table|
|000044e0| 20 73 69 7a 65 20 2a 2f | 0d 20 20 20 20 20 20 20 | size */|. |
|000044f0| 20 69 66 20 28 28 66 20 | 3d 20 31 20 3c 3c 20 28 | if ((f |= 1 << (|
|00004500| 6a 20 3d 20 6b 20 2d 20 | 77 29 29 20 3e 20 61 20 |j = k - |w)) > a |
|00004510| 2b 20 31 29 20 20 20 20 | 20 2f 2a 20 74 72 79 20 |+ 1) | /* try |
|00004520| 61 20 6b 2d 77 20 62 69 | 74 20 74 61 62 6c 65 20 |a k-w bi|t table |
|00004530| 2a 2f 0d 20 20 20 20 20 | 20 20 20 7b 20 20 20 20 |*/. | { |
|00004540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004550| 20 20 20 2f 2a 20 74 6f | 6f 20 66 65 77 20 63 6f | /* to|o few co|
|00004560| 64 65 73 20 66 6f 72 20 | 6b 2d 77 20 62 69 74 20 |des for |k-w bit |
|00004570| 74 61 62 6c 65 20 2a 2f | 0d 20 20 20 20 20 20 20 |table */|. |
|00004580| 20 20 20 66 20 2d 3d 20 | 61 20 2b 20 31 3b 20 20 | f -= |a + 1; |
|00004590| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 64 65 64 75 | | /* dedu|
|000045a0| 63 74 20 63 6f 64 65 73 | 20 66 72 6f 6d 20 70 61 |ct codes| from pa|
|000045b0| 74 74 65 72 6e 73 20 6c | 65 66 74 20 2a 2f 0d 20 |tterns l|eft */. |
|000045c0| 20 20 20 20 20 20 20 20 | 20 78 70 20 3d 20 63 20 | | xp = c |
|000045d0| 2b 20 6b 3b 0d 20 20 20 | 20 20 20 20 20 20 20 77 |+ k;. | w|
|000045e0| 68 69 6c 65 20 28 2b 2b | 6a 20 3c 20 7a 29 20 20 |hile (++|j < z) |
|000045f0| 20 20 20 20 20 2f 2a 20 | 74 72 79 20 73 6d 61 6c | /* |try smal|
|00004600| 6c 65 72 20 74 61 62 6c | 65 73 20 75 70 20 74 6f |ler tabl|es up to|
|00004610| 20 7a 20 62 69 74 73 20 | 2a 2f 0d 20 20 20 20 20 | z bits |*/. |
|00004620| 20 20 20 20 20 7b 0d 20 | 20 20 20 20 20 20 20 20 | {. | |
|00004630| 20 20 20 69 66 20 28 28 | 66 20 3c 3c 3d 20 31 29 | if ((|f <<= 1)|
|00004640| 20 3c 3d 20 2a 2b 2b 78 | 70 29 0d 20 20 20 20 20 | <= *++x|p). |
|00004650| 20 20 20 20 20 20 20 20 | 20 62 72 65 61 6b 3b 20 | | break; |
|00004660| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 65 6e | | /* en|
|00004670| 6f 75 67 68 20 63 6f 64 | 65 73 20 74 6f 20 75 73 |ough cod|es to us|
|00004680| 65 20 75 70 20 6a 20 62 | 69 74 73 20 2a 2f 0d 20 |e up j b|its */. |
|00004690| 20 20 20 20 20 20 20 20 | 20 20 20 66 20 2d 3d 20 | | f -= |
|000046a0| 2a 78 70 3b 20 20 20 20 | 20 20 20 20 20 20 20 2f |*xp; | /|
|000046b0| 2a 20 65 6c 73 65 20 64 | 65 64 75 63 74 20 63 6f |* else d|educt co|
|000046c0| 64 65 73 20 66 72 6f 6d | 20 70 61 74 74 65 72 6e |des from| pattern|
|000046d0| 73 20 2a 2f 0d 20 20 20 | 20 20 20 20 20 20 20 7d |s */. | }|
|000046e0| 0d 20 20 20 20 20 20 20 | 20 7d 0d 20 20 20 20 20 |. | }. |
|000046f0| 20 20 20 7a 20 3d 20 31 | 20 3c 3c 20 6a 3b 20 20 | z = 1| << j; |
|00004700| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 74 61 | | /* ta|
|00004710| 62 6c 65 20 65 6e 74 72 | 69 65 73 20 66 6f 72 20 |ble entr|ies for |
|00004720| 6a 2d 62 69 74 20 74 61 | 62 6c 65 20 2a 2f 0d 0d |j-bit ta|ble */..|
|00004730| 20 20 20 20 20 20 20 20 | 2f 2a 20 61 6c 6c 6f 63 | |/* alloc|
|00004740| 61 74 65 20 61 6e 64 20 | 6c 69 6e 6b 20 69 6e 20 |ate and |link in |
|00004750| 6e 65 77 20 74 61 62 6c | 65 20 2a 2f 0d 20 20 20 |new tabl|e */. |
|00004760| 20 20 20 20 20 69 66 20 | 28 28 71 20 3d 20 28 73 | if |((q = (s|
|00004770| 74 72 75 63 74 20 68 75 | 66 74 20 2a 29 6d 61 6c |truct hu|ft *)mal|
|00004780| 6c 6f 63 28 28 7a 20 2b | 20 31 29 2a 73 69 7a 65 |loc((z +| 1)*size|
|00004790| 6f 66 28 73 74 72 75 63 | 74 20 68 75 66 74 29 29 |of(struc|t huft))|
|000047a0| 29 20 3d 3d 0d 20 20 20 | 20 20 20 20 20 20 20 20 |) ==. | |
|000047b0| 20 28 73 74 72 75 63 74 | 20 68 75 66 74 20 2a 29 | (struct| huft *)|
|000047c0| 4e 55 4c 4c 29 0d 20 20 | 20 20 20 20 20 20 7b 0d |NULL). | {.|
|000047d0| 20 20 20 20 20 20 20 20 | 20 20 69 66 20 28 68 29 | | if (h)|
|000047e0| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 68 75 66 |. | huf|
|000047f0| 74 5f 66 72 65 65 28 75 | 5b 30 5d 29 3b 0d 20 20 |t_free(u|[0]);. |
|00004800| 20 20 20 20 20 20 20 20 | 72 65 74 75 72 6e 20 33 | |return 3|
|00004810| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a |; | /*|
|00004820| 20 6e 6f 74 20 65 6e 6f | 75 67 68 20 6d 65 6d 6f | not eno|ugh memo|
|00004830| 72 79 20 2a 2f 0d 20 20 | 20 20 20 20 20 20 7d 0d |ry */. | }.|
|00004840| 20 20 20 20 20 20 20 20 | 68 75 66 74 73 20 2b 3d | |hufts +=|
|00004850| 20 7a 20 2b 20 31 3b 20 | 20 20 20 20 20 20 20 20 | z + 1; | |
|00004860| 2f 2a 20 74 72 61 63 6b | 20 6d 65 6d 6f 72 79 20 |/* track| memory |
|00004870| 75 73 61 67 65 20 2a 2f | 0d 20 20 20 20 20 20 20 |usage */|. |
|00004880| 20 2a 74 20 3d 20 71 20 | 2b 20 31 3b 20 20 20 20 | *t = q |+ 1; |
|00004890| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 6c 69 6e 6b | | /* link|
|000048a0| 20 74 6f 20 6c 69 73 74 | 20 66 6f 72 20 68 75 66 | to list| for huf|
|000048b0| 74 5f 66 72 65 65 28 29 | 20 2a 2f 0d 20 20 20 20 |t_free()| */. |
|000048c0| 20 20 20 20 2a 28 74 20 | 3d 20 26 28 71 2d 3e 76 | *(t |= &(q->v|
|000048d0| 2e 74 29 29 20 3d 20 28 | 73 74 72 75 63 74 20 68 |.t)) = (|struct h|
|000048e0| 75 66 74 20 2a 29 4e 55 | 4c 4c 3b 0d 20 20 20 20 |uft *)NU|LL;. |
|000048f0| 20 20 20 20 75 5b 68 5d | 20 3d 20 2b 2b 71 3b 20 | u[h]| = ++q; |
|00004900| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 74 | | /* t|
|00004910| 61 62 6c 65 20 73 74 61 | 72 74 73 20 61 66 74 65 |able sta|rts afte|
|00004920| 72 20 6c 69 6e 6b 20 2a | 2f 0d 0d 20 20 20 20 20 |r link *|/.. |
|00004930| 20 20 20 2f 2a 20 63 6f | 6e 6e 65 63 74 20 74 6f | /* co|nnect to|
|00004940| 20 6c 61 73 74 20 74 61 | 62 6c 65 2c 20 69 66 20 | last ta|ble, if |
|00004950| 74 68 65 72 65 20 69 73 | 20 6f 6e 65 20 2a 2f 0d |there is| one */.|
|00004960| 20 20 20 20 20 20 20 20 | 69 66 20 28 68 29 0d 20 | |if (h). |
|00004970| 20 20 20 20 20 20 20 7b | 0d 20 20 20 20 20 20 20 | {|. |
|00004980| 20 20 20 78 5b 68 5d 20 | 3d 20 69 3b 20 20 20 20 | x[h] |= i; |
|00004990| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 73 61 76 65 | | /* save|
|000049a0| 20 70 61 74 74 65 72 6e | 20 66 6f 72 20 62 61 63 | pattern| for bac|
|000049b0| 6b 69 6e 67 20 75 70 20 | 2a 2f 0d 20 20 20 20 20 |king up |*/. |
|000049c0| 20 20 20 20 20 72 2e 62 | 20 3d 20 28 75 63 68 29 | r.b| = (uch)|
|000049d0| 6c 3b 20 20 20 20 20 20 | 20 20 20 2f 2a 20 62 69 |l; | /* bi|
|000049e0| 74 73 20 74 6f 20 64 75 | 6d 70 20 62 65 66 6f 72 |ts to du|mp befor|
|000049f0| 65 20 74 68 69 73 20 74 | 61 62 6c 65 20 2a 2f 0d |e this t|able */.|
|00004a00| 20 20 20 20 20 20 20 20 | 20 20 72 2e 65 20 3d 20 | | r.e = |
|00004a10| 28 75 63 68 29 28 31 36 | 20 2b 20 6a 29 3b 20 20 |(uch)(16| + j); |
|00004a20| 2f 2a 20 62 69 74 73 20 | 69 6e 20 74 68 69 73 20 |/* bits |in this |
|00004a30| 74 61 62 6c 65 20 2a 2f | 0d 20 20 20 20 20 20 20 |table */|. |
|00004a40| 20 20 20 72 2e 76 2e 74 | 20 3d 20 71 3b 20 20 20 | r.v.t| = q; |
|00004a50| 20 20 20 20 20 20 20 20 | 20 2f 2a 20 70 6f 69 6e | | /* poin|
|00004a60| 74 65 72 20 74 6f 20 74 | 68 69 73 20 74 61 62 6c |ter to t|his tabl|
|00004a70| 65 20 2a 2f 0d 20 20 20 | 20 20 20 20 20 20 20 6a |e */. | j|
|00004a80| 20 3d 20 69 20 3e 3e 20 | 28 77 20 2d 20 6c 29 3b | = i >> |(w - l);|
|00004a90| 20 20 20 20 20 2f 2a 20 | 28 67 65 74 20 61 72 6f | /* |(get aro|
|00004aa0| 75 6e 64 20 54 75 72 62 | 6f 20 43 20 62 75 67 29 |und Turb|o C bug)|
|00004ab0| 20 2a 2f 0d 20 20 20 20 | 20 20 20 20 20 20 75 5b | */. | u[|
|00004ac0| 68 2d 31 5d 5b 6a 5d 20 | 3d 20 72 3b 20 20 20 20 |h-1][j] |= r; |
|00004ad0| 20 20 20 20 2f 2a 20 63 | 6f 6e 6e 65 63 74 20 74 | /* c|onnect t|
|00004ae0| 6f 20 6c 61 73 74 20 74 | 61 62 6c 65 20 2a 2f 0d |o last t|able */.|
|00004af0| 20 20 20 20 20 20 20 20 | 7d 0d 20 20 20 20 20 20 | |}. |
|00004b00| 7d 0d 0d 20 20 20 20 20 | 20 2f 2a 20 73 65 74 20 |}.. | /* set |
|00004b10| 75 70 20 74 61 62 6c 65 | 20 65 6e 74 72 79 20 69 |up table| entry i|
|00004b20| 6e 20 72 20 2a 2f 0d 20 | 20 20 20 20 20 72 2e 62 |n r */. | r.b|
|00004b30| 20 3d 20 28 75 63 68 29 | 28 6b 20 2d 20 77 29 3b | = (uch)|(k - w);|
|00004b40| 0d 20 20 20 20 20 20 69 | 66 20 28 70 20 3e 3d 20 |. i|f (p >= |
|00004b50| 76 20 2b 20 6e 29 0d 20 | 20 20 20 20 20 20 20 72 |v + n). | r|
|00004b60| 2e 65 20 3d 20 39 39 3b | 20 20 20 20 20 20 20 20 |.e = 99;| |
|00004b70| 20 20 20 20 20 20 20 2f | 2a 20 6f 75 74 20 6f 66 | /|* out of|
|00004b80| 20 76 61 6c 75 65 73 2d | 2d 69 6e 76 61 6c 69 64 | values-|-invalid|
|00004b90| 20 63 6f 64 65 20 2a 2f | 0d 20 20 20 20 20 20 65 | code */|. e|
|00004ba0| 6c 73 65 20 69 66 20 28 | 2a 70 20 3c 20 73 29 0d |lse if (|*p < s).|
|00004bb0| 20 20 20 20 20 20 7b 0d | 20 20 20 20 20 20 20 20 | {.| |
|00004bc0| 72 2e 65 20 3d 20 28 75 | 63 68 29 28 2a 70 20 3c |r.e = (u|ch)(*p <|
|00004bd0| 20 32 35 36 20 3f 20 31 | 36 20 3a 20 31 35 29 3b | 256 ? 1|6 : 15);|
|00004be0| 20 20 20 20 2f 2a 20 32 | 35 36 20 69 73 20 65 6e | /* 2|56 is en|
|00004bf0| 64 2d 6f 66 2d 62 6c 6f | 63 6b 20 63 6f 64 65 20 |d-of-blo|ck code |
|00004c00| 2a 2f 0d 20 20 20 20 20 | 20 20 20 72 2e 76 2e 6e |*/. | r.v.n|
|00004c10| 20 3d 20 28 75 73 68 29 | 28 2a 70 29 3b 20 20 20 | = (ush)|(*p); |
|00004c20| 20 20 20 20 20 20 20 20 | 20 20 2f 2a 20 73 69 6d | | /* sim|
|00004c30| 70 6c 65 20 63 6f 64 65 | 20 69 73 20 6a 75 73 74 |ple code| is just|
|00004c40| 20 74 68 65 20 76 61 6c | 75 65 20 2a 2f 0d 09 70 | the val|ue */..p|
|00004c50| 2b 2b 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |++; | |
|00004c60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 2f 2a | | /*|
|00004c70| 20 6f 6e 65 20 63 6f 6d | 70 69 6c 65 72 20 64 6f | one com|piler do|
|00004c80| 65 73 20 6e 6f 74 20 6c | 69 6b 65 20 2a 70 2b 2b |es not l|ike *p++|
|00004c90| 20 2a 2f 0d 20 20 20 20 | 20 20 7d 0d 20 20 20 20 | */. | }. |
|00004ca0| 20 20 65 6c 73 65 0d 20 | 20 20 20 20 20 7b 0d 20 | else. | {. |
|00004cb0| 20 20 20 20 20 20 20 72 | 2e 65 20 3d 20 28 75 63 | r|.e = (uc|
|00004cc0| 68 29 65 5b 2a 70 20 2d | 20 73 5d 3b 20 20 20 2f |h)e[*p -| s]; /|
|00004cd0| 2a 20 6e 6f 6e 2d 73 69 | 6d 70 6c 65 2d 2d 6c 6f |* non-si|mple--lo|
|00004ce0| 6f 6b 20 75 70 20 69 6e | 20 6c 69 73 74 73 20 2a |ok up in| lists *|
|00004cf0| 2f 0d 20 20 20 20 20 20 | 20 20 72 2e 76 2e 6e 20 |/. | r.v.n |
|00004d00| 3d 20 64 5b 2a 70 2b 2b | 20 2d 20 73 5d 3b 0d 20 |= d[*p++| - s];. |
|00004d10| 20 20 20 20 20 7d 0d 0d | 20 20 20 20 20 20 2f 2a | }..| /*|
|00004d20| 20 66 69 6c 6c 20 63 6f | 64 65 2d 6c 69 6b 65 20 | fill co|de-like |
|00004d30| 65 6e 74 72 69 65 73 20 | 77 69 74 68 20 72 20 2a |entries |with r *|
|00004d40| 2f 0d 20 20 20 20 20 20 | 66 20 3d 20 31 20 3c 3c |/. |f = 1 <<|
|00004d50| 20 28 6b 20 2d 20 77 29 | 3b 0d 20 20 20 20 20 20 | (k - w)|;. |
|00004d60| 66 6f 72 20 28 6a 20 3d | 20 69 20 3e 3e 20 77 3b |for (j =| i >> w;|
|00004d70| 20 6a 20 3c 20 7a 3b 20 | 6a 20 2b 3d 20 66 29 0d | j < z; |j += f).|
|00004d80| 20 20 20 20 20 20 20 20 | 71 5b 6a 5d 20 3d 20 72 | |q[j] = r|
|00004d90| 3b 0d 0d 20 20 20 20 20 | 20 2f 2a 20 62 61 63 6b |;.. | /* back|
|00004da0| 77 61 72 64 73 20 69 6e | 63 72 65 6d 65 6e 74 20 |wards in|crement |
|00004db0| 74 68 65 20 6b 2d 62 69 | 74 20 63 6f 64 65 20 69 |the k-bi|t code i|
|00004dc0| 20 2a 2f 0d 20 20 20 20 | 20 20 66 6f 72 20 28 6a | */. | for (j|
|00004dd0| 20 3d 20 31 20 3c 3c 20 | 28 6b 20 2d 20 31 29 3b | = 1 << |(k - 1);|
|00004de0| 20 69 20 26 20 6a 3b 20 | 6a 20 3e 3e 3d 20 31 29 | i & j; |j >>= 1)|
|00004df0| 0d 20 20 20 20 20 20 20 | 20 69 20 5e 3d 20 6a 3b |. | i ^= j;|
|00004e00| 0d 20 20 20 20 20 20 69 | 20 5e 3d 20 6a 3b 0d 0d |. i| ^= j;..|
|00004e10| 20 20 20 20 20 20 2f 2a | 20 62 61 63 6b 75 70 20 | /*| backup |
|00004e20| 6f 76 65 72 20 66 69 6e | 69 73 68 65 64 20 74 61 |over fin|ished ta|
|00004e30| 62 6c 65 73 20 2a 2f 0d | 20 20 20 20 20 20 77 68 |bles */.| wh|
|00004e40| 69 6c 65 20 28 28 69 20 | 26 20 28 28 31 20 3c 3c |ile ((i |& ((1 <<|
|00004e50| 20 77 29 20 2d 20 31 29 | 29 20 21 3d 20 78 5b 68 | w) - 1)|) != x[h|
|00004e60| 5d 29 0d 20 20 20 20 20 | 20 7b 0d 20 20 20 20 20 |]). | {. |
|00004e70| 20 20 20 68 2d 2d 3b 20 | 20 20 20 20 20 20 20 20 | h--; | |
|00004e80| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 64 6f | | /* do|
|00004e90| 6e 27 74 20 6e 65 65 64 | 20 74 6f 20 75 70 64 61 |n't need| to upda|
|00004ea0| 74 65 20 71 20 2a 2f 0d | 20 20 20 20 20 20 20 20 |te q */.| |
|00004eb0| 77 20 2d 3d 20 6c 3b 0d | 20 20 20 20 20 20 7d 0d |w -= l;.| }.|
|00004ec0| 20 20 20 20 7d 0d 20 20 | 7d 0d 0d 0d 20 20 2f 2a | }. |}... /*|
|00004ed0| 20 52 65 74 75 72 6e 20 | 74 72 75 65 20 28 31 29 | Return |true (1)|
|00004ee0| 20 69 66 20 77 65 20 77 | 65 72 65 20 67 69 76 65 | if we w|ere give|
|00004ef0| 6e 20 61 6e 20 69 6e 63 | 6f 6d 70 6c 65 74 65 20 |n an inc|omplete |
|00004f00| 74 61 62 6c 65 20 2a 2f | 0d 20 20 72 65 74 75 72 |table */|. retur|
|00004f10| 6e 20 79 20 21 3d 20 30 | 20 26 26 20 67 20 21 3d |n y != 0| && g !=|
|00004f20| 20 31 3b 0d 7d 0d 0d 0d | 0d 69 6e 74 20 68 75 66 | 1;.}...|.int huf|
|00004f30| 74 5f 66 72 65 65 28 74 | 29 0d 73 74 72 75 63 74 |t_free(t|).struct|
|00004f40| 20 68 75 66 74 20 2a 74 | 3b 20 20 20 20 20 20 20 | huft *t|; |
|00004f50| 20 20 2f 2a 20 74 61 62 | 6c 65 20 74 6f 20 66 72 | /* tab|le to fr|
|00004f60| 65 65 20 2a 2f 0d 2f 2a | 20 46 72 65 65 20 74 68 |ee */./*| Free th|
|00004f70| 65 20 6d 61 6c 6c 6f 63 | 27 65 64 20 74 61 62 6c |e malloc|'ed tabl|
|00004f80| 65 73 20 62 75 69 6c 74 | 20 62 79 20 68 75 66 74 |es built| by huft|
|00004f90| 5f 62 75 69 6c 64 28 29 | 2c 20 77 68 69 63 68 20 |_build()|, which |
|00004fa0| 6d 61 6b 65 73 20 61 20 | 6c 69 6e 6b 65 64 0d 20 |makes a |linked. |
|00004fb0| 20 20 6c 69 73 74 20 6f | 66 20 74 68 65 20 74 61 | list o|f the ta|
|00004fc0| 62 6c 65 73 20 69 74 20 | 6d 61 64 65 2c 20 77 69 |bles it |made, wi|
|00004fd0| 74 68 20 74 68 65 20 6c | 69 6e 6b 73 20 69 6e 20 |th the l|inks in |
|00004fe0| 61 20 64 75 6d 6d 79 20 | 66 69 72 73 74 20 65 6e |a dummy |first en|
|00004ff0| 74 72 79 20 6f 66 0d 20 | 20 20 65 61 63 68 20 74 |try of. | each t|
|00005000| 61 62 6c 65 2e 20 2a 2f | 0d 7b 0d 20 20 72 65 67 |able. */|.{. reg|
|00005010| 69 73 74 65 72 20 73 74 | 72 75 63 74 20 68 75 66 |ister st|ruct huf|
|00005020| 74 20 2a 70 2c 20 2a 71 | 3b 0d 0d 0d 20 20 2f 2a |t *p, *q|;... /*|
|00005030| 20 47 6f 20 74 68 72 6f | 75 67 68 20 6c 69 6e 6b | Go thro|ugh link|
|00005040| 65 64 20 6c 69 73 74 2c | 20 66 72 65 65 69 6e 67 |ed list,| freeing|
|00005050| 20 66 72 6f 6d 20 74 68 | 65 20 6d 61 6c 6c 6f 63 | from th|e malloc|
|00005060| 65 64 20 28 74 5b 2d 31 | 5d 29 20 61 64 64 72 65 |ed (t[-1|]) addre|
|00005070| 73 73 2e 20 2a 2f 0d 20 | 20 70 20 3d 20 74 3b 0d |ss. */. | p = t;.|
|00005080| 20 20 77 68 69 6c 65 20 | 28 70 20 21 3d 20 28 73 | while |(p != (s|
|00005090| 74 72 75 63 74 20 68 75 | 66 74 20 2a 29 4e 55 4c |truct hu|ft *)NUL|
|000050a0| 4c 29 0d 20 20 7b 0d 20 | 20 20 20 71 20 3d 20 28 |L). {. | q = (|
|000050b0| 2d 2d 70 29 2d 3e 76 2e | 74 3b 0d 20 20 20 20 66 |--p)->v.|t;. f|
|000050c0| 72 65 65 28 28 63 68 61 | 72 2a 29 70 29 3b 0d 20 |ree((cha|r*)p);. |
|000050d0| 20 20 20 70 20 3d 20 71 | 3b 0d 20 20 7d 20 0d 20 | p = q|;. } . |
|000050e0| 20 72 65 74 75 72 6e 20 | 30 3b 0d 7d 0d 0d 0d 69 | return |0;.}...i|
|000050f0| 6e 74 20 69 6e 66 6c 61 | 74 65 5f 63 6f 64 65 73 |nt infla|te_codes|
|00005100| 28 74 6c 2c 20 74 64 2c | 20 62 6c 2c 20 62 64 29 |(tl, td,| bl, bd)|
|00005110| 0d 73 74 72 75 63 74 20 | 68 75 66 74 20 2a 74 6c |.struct |huft *tl|
|00005120| 2c 20 2a 74 64 3b 20 20 | 20 2f 2a 20 6c 69 74 65 |, *td; | /* lite|
|00005130| 72 61 6c 2f 6c 65 6e 67 | 74 68 20 61 6e 64 20 64 |ral/leng|th and d|
|00005140| 69 73 74 61 6e 63 65 20 | 64 65 63 6f 64 65 72 20 |istance |decoder |
|00005150| 74 61 62 6c 65 73 20 2a | 2f 0d 69 6e 74 20 62 6c |tables *|/.int bl|
|00005160| 2c 20 62 64 3b 20 20 20 | 20 20 20 20 20 20 20 20 |, bd; | |
|00005170| 20 20 2f 2a 20 6e 75 6d | 62 65 72 20 6f 66 20 62 | /* num|ber of b|
|00005180| 69 74 73 20 64 65 63 6f | 64 65 64 20 62 79 20 74 |its deco|ded by t|
|00005190| 6c 5b 5d 20 61 6e 64 20 | 74 64 5b 5d 20 2a 2f 0d |l[] and |td[] */.|
|000051a0| 2f 2a 20 69 6e 66 6c 61 | 74 65 20 28 64 65 63 6f |/* infla|te (deco|
|000051b0| 6d 70 72 65 73 73 29 20 | 74 68 65 20 63 6f 64 65 |mpress) |the code|
|000051c0| 73 20 69 6e 20 61 20 64 | 65 66 6c 61 74 65 64 20 |s in a d|eflated |
|000051d0| 28 63 6f 6d 70 72 65 73 | 73 65 64 29 20 62 6c 6f |(compres|sed) blo|
|000051e0| 63 6b 2e 0d 20 20 20 52 | 65 74 75 72 6e 20 61 6e |ck.. R|eturn an|
|000051f0| 20 65 72 72 6f 72 20 63 | 6f 64 65 20 6f 72 20 7a | error c|ode or z|
|00005200| 65 72 6f 20 69 66 20 69 | 74 20 61 6c 6c 20 67 6f |ero if i|t all go|
|00005210| 65 73 20 6f 6b 2e 20 2a | 2f 0d 7b 0d 20 20 72 65 |es ok. *|/.{. re|
|00005220| 67 69 73 74 65 72 20 75 | 6e 73 69 67 6e 65 64 20 |gister u|nsigned |
|00005230| 65 3b 20 20 2f 2a 20 74 | 61 62 6c 65 20 65 6e 74 |e; /* t|able ent|
|00005240| 72 79 20 66 6c 61 67 2f | 6e 75 6d 62 65 72 20 6f |ry flag/|number o|
|00005250| 66 20 65 78 74 72 61 20 | 62 69 74 73 20 2a 2f 0d |f extra |bits */.|
|00005260| 20 20 75 6e 73 69 67 6e | 65 64 20 6e 2c 20 64 3b | unsign|ed n, d;|
|00005270| 20 20 20 20 20 20 20 20 | 2f 2a 20 6c 65 6e 67 74 | |/* lengt|
|00005280| 68 20 61 6e 64 20 69 6e | 64 65 78 20 66 6f 72 20 |h and in|dex for |
|00005290| 63 6f 70 79 20 2a 2f 0d | 20 20 75 6e 73 69 67 6e |copy */.| unsign|
|000052a0| 65 64 20 77 3b 20 20 20 | 20 20 20 20 20 20 20 20 |ed w; | |
|000052b0| 2f 2a 20 63 75 72 72 65 | 6e 74 20 77 69 6e 64 6f |/* curre|nt windo|
|000052c0| 77 20 70 6f 73 69 74 69 | 6f 6e 20 2a 2f 0d 20 20 |w positi|on */. |
|000052d0| 73 74 72 75 63 74 20 68 | 75 66 74 20 2a 74 3b 20 |struct h|uft *t; |
|000052e0| 20 20 20 20 20 20 2f 2a | 20 70 6f 69 6e 74 65 72 | /*| pointer|
|000052f0| 20 74 6f 20 74 61 62 6c | 65 20 65 6e 74 72 79 20 | to tabl|e entry |
|00005300| 2a 2f 0d 20 20 75 6e 73 | 69 67 6e 65 64 20 6d 6c |*/. uns|igned ml|
|00005310| 2c 20 6d 64 3b 20 20 20 | 20 20 20 2f 2a 20 6d 61 |, md; | /* ma|
|00005320| 73 6b 73 20 66 6f 72 20 | 62 6c 20 61 6e 64 20 62 |sks for |bl and b|
|00005330| 64 20 62 69 74 73 20 2a | 2f 0d 20 20 72 65 67 69 |d bits *|/. regi|
|00005340| 73 74 65 72 20 75 6c 67 | 20 62 3b 20 20 20 20 20 |ster ulg| b; |
|00005350| 20 20 2f 2a 20 62 69 74 | 20 62 75 66 66 65 72 20 | /* bit| buffer |
|00005360| 2a 2f 0d 20 20 72 65 67 | 69 73 74 65 72 20 75 6e |*/. reg|ister un|
|00005370| 73 69 67 6e 65 64 20 6b | 3b 20 20 2f 2a 20 6e 75 |signed k|; /* nu|
|00005380| 6d 62 65 72 20 6f 66 20 | 62 69 74 73 20 69 6e 20 |mber of |bits in |
|00005390| 62 69 74 20 62 75 66 66 | 65 72 20 2a 2f 0d 0d 0d |bit buff|er */...|
|000053a0| 20 20 2f 2a 20 6d 61 6b | 65 20 6c 6f 63 61 6c 20 | /* mak|e local |
|000053b0| 63 6f 70 69 65 73 20 6f | 66 20 67 6c 6f 62 61 6c |copies o|f global|
|000053c0| 73 20 2a 2f 0d 20 20 62 | 20 3d 20 62 62 3b 20 20 |s */. b| = bb; |
|000053d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000053e0| 20 20 20 20 20 2f 2a 20 | 69 6e 69 74 69 61 6c 69 | /* |initiali|
|000053f0| 7a 65 20 62 69 74 20 62 | 75 66 66 65 72 20 2a 2f |ze bit b|uffer */|
|00005400| 0d 20 20 6b 20 3d 20 62 | 6b 3b 0d 20 20 77 20 3d |. k = b|k;. w =|
|00005410| 20 77 70 3b 20 20 20 20 | 20 20 20 20 20 20 20 20 | wp; | |
|00005420| 20 20 20 20 20 20 20 20 | 20 20 20 2f 2a 20 69 6e | | /* in|
|00005430| 69 74 69 61 6c 69 7a 65 | 20 77 69 6e 64 6f 77 20 |itialize| window |
|00005440| 70 6f 73 69 74 69 6f 6e | 20 2a 2f 0d 0d 20 20 2f |position| */.. /|
|00005450| 2a 20 69 6e 66 6c 61 74 | 65 20 74 68 65 20 63 6f |* inflat|e the co|
|00005460| 64 65 64 20 64 61 74 61 | 20 2a 2f 0d 20 20 6d 6c |ded data| */. ml|
|00005470| 20 3d 20 6d 61 73 6b 5f | 62 69 74 73 5b 62 6c 5d | = mask_|bits[bl]|
|00005480| 3b 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 70 |; | /* p|
|00005490| 72 65 63 6f 6d 70 75 74 | 65 20 6d 61 73 6b 73 20 |recomput|e masks |
|000054a0| 66 6f 72 20 73 70 65 65 | 64 20 2a 2f 0d 20 20 6d |for spee|d */. m|
|000054b0| 64 20 3d 20 6d 61 73 6b | 5f 62 69 74 73 5b 62 64 |d = mask|_bits[bd|
|000054c0| 5d 3b 0d 20 20 66 6f 72 | 20 28 3b 3b 29 20 20 20 |];. for| (;;) |
|000054d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000054e0| 20 20 20 2f 2a 20 64 6f | 20 75 6e 74 69 6c 20 65 | /* do| until e|
|000054f0| 6e 64 20 6f 66 20 62 6c | 6f 63 6b 20 2a 2f 0d 20 |nd of bl|ock */. |
|00005500| 20 7b 0d 20 20 20 20 4e | 45 45 44 42 49 54 53 28 | {. N|EEDBITS(|
|00005510| 28 75 6e 73 69 67 6e 65 | 64 29 62 6c 29 0d 20 20 |(unsigne|d)bl). |
|00005520| 20 20 69 66 20 28 28 65 | 20 3d 20 28 74 20 3d 20 | if ((e| = (t = |
|00005530| 74 6c 20 2b 20 28 28 75 | 6e 73 69 67 6e 65 64 29 |tl + ((u|nsigned)|
|00005540| 62 20 26 20 6d 6c 29 29 | 2d 3e 65 29 20 3e 20 31 |b & ml))|->e) > 1|
|00005550| 36 29 0d 20 20 20 20 20 | 20 64 6f 20 7b 0d 20 20 |6). | do {. |
|00005560| 20 20 20 20 20 20 69 66 | 20 28 65 20 3d 3d 20 39 | if| (e == 9|
|00005570| 39 29 0d 20 20 20 20 20 | 20 20 20 20 20 72 65 74 |9). | ret|
|00005580| 75 72 6e 20 31 3b 0d 20 | 20 20 20 20 20 20 20 44 |urn 1;. | D|
|00005590| 55 4d 50 42 49 54 53 28 | 74 2d 3e 62 29 0d 20 20 |UMPBITS(|t->b). |
|000055a0| 20 20 20 20 20 20 65 20 | 2d 3d 20 31 36 3b 0d 20 | e |-= 16;. |
|000055b0| 20 20 20 20 20 20 20 4e | 45 45 44 42 49 54 53 28 | N|EEDBITS(|
|000055c0| 65 29 0d 20 20 20 20 20 | 20 7d 20 77 68 69 6c 65 |e). | } while|
|000055d0| 20 28 28 65 20 3d 20 28 | 74 20 3d 20 74 2d 3e 76 | ((e = (|t = t->v|
|000055e0| 2e 74 20 2b 20 28 28 75 | 6e 73 69 67 6e 65 64 29 |.t + ((u|nsigned)|
|000055f0| 62 20 26 20 6d 61 73 6b | 5f 62 69 74 73 5b 65 5d |b & mask|_bits[e]|
|00005600| 29 29 2d 3e 65 29 20 3e | 20 31 36 29 3b 0d 20 20 |))->e) >| 16);. |
|00005610| 20 20 44 55 4d 50 42 49 | 54 53 28 74 2d 3e 62 29 | DUMPBI|TS(t->b)|
|00005620| 0d 20 20 20 20 69 66 20 | 28 65 20 3d 3d 20 31 36 |. if |(e == 16|
|00005630| 29 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |) | |
|00005640| 20 2f 2a 20 74 68 65 6e | 20 69 74 27 73 20 61 20 | /* then| it's a |
|00005650| 6c 69 74 65 72 61 6c 20 | 2a 2f 0d 20 20 20 20 7b |literal |*/. {|
|00005660| 0d 20 20 20 20 20 20 73 | 6c 69 64 65 5b 77 2b 2b |. s|lide[w++|
|00005670| 5d 20 3d 20 28 75 63 68 | 29 74 2d 3e 76 2e 6e 3b |] = (uch|)t->v.n;|
|00005680| 0d 20 20 20 20 20 20 54 | 72 61 63 65 76 76 28 28 |. T|racevv((|
|00005690| 73 74 64 65 72 72 2c 20 | 22 25 63 22 2c 20 73 6c |stderr, |"%c", sl|
|000056a0| 69 64 65 5b 77 2d 31 5d | 29 29 3b 0d 20 20 20 20 |ide[w-1]|));. |
|000056b0| 20 20 69 66 20 28 77 20 | 3d 3d 20 57 53 49 5a 45 | if (w |== WSIZE|
|000056c0| 29 0d 20 20 20 20 20 20 | 7b 0d 20 20 20 20 20 20 |). |{. |
|000056d0| 20 20 66 6c 75 73 68 5f | 6f 75 74 70 75 74 28 77 | flush_|output(w|
|000056e0| 29 3b 0d 20 20 20 20 20 | 20 20 20 77 20 3d 20 30 |);. | w = 0|
|000056f0| 3b 0d 20 20 20 20 20 20 | 7d 0d 20 20 20 20 7d 0d |;. |}. }.|
|00005700| 20 20 20 20 65 6c 73 65 | 20 20 20 20 20 20 20 20 | else| |
|00005710| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005720| 2f 2a 20 69 74 27 73 20 | 61 6e 20 45 4f 42 20 6f |/* it's |an EOB o|
|00005730| 72 20 61 20 6c 65 6e 67 | 74 68 20 2a 2f 0d 20 20 |r a leng|th */. |
|00005740| 20 20 7b 0d 20 20 20 20 | 20 20 2f 2a 20 65 78 69 | {. | /* exi|
|00005750| 74 20 69 66 20 65 6e 64 | 20 6f 66 20 62 6c 6f 63 |t if end| of bloc|
|00005760| 6b 20 2a 2f 0d 20 20 20 | 20 20 20 69 66 20 28 65 |k */. | if (e|
|00005770| 20 3d 3d 20 31 35 29 0d | 20 20 20 20 20 20 20 20 | == 15).| |
|00005780| 62 72 65 61 6b 3b 0d 0d | 20 20 20 20 20 20 2f 2a |break;..| /*|
|00005790| 20 67 65 74 20 6c 65 6e | 67 74 68 20 6f 66 20 62 | get len|gth of b|
|000057a0| 6c 6f 63 6b 20 74 6f 20 | 63 6f 70 79 20 2a 2f 0d |lock to |copy */.|
|000057b0| 20 20 20 20 20 20 4e 45 | 45 44 42 49 54 53 28 65 | NE|EDBITS(e|
|000057c0| 29 0d 20 20 20 20 20 20 | 6e 20 3d 20 74 2d 3e 76 |). |n = t->v|
|000057d0| 2e 6e 20 2b 20 28 28 75 | 6e 73 69 67 6e 65 64 29 |.n + ((u|nsigned)|
|000057e0| 62 20 26 20 6d 61 73 6b | 5f 62 69 74 73 5b 65 5d |b & mask|_bits[e]|
|000057f0| 29 3b 0d 20 20 20 20 20 | 20 44 55 4d 50 42 49 54 |);. | DUMPBIT|
|00005800| 53 28 65 29 3b 0d 0d 20 | 20 20 20 20 20 2f 2a 20 |S(e);.. | /* |
|00005810| 64 65 63 6f 64 65 20 64 | 69 73 74 61 6e 63 65 20 |decode d|istance |
|00005820| 6f 66 20 62 6c 6f 63 6b | 20 74 6f 20 63 6f 70 79 |of block| to copy|
|00005830| 20 2a 2f 0d 20 20 20 20 | 20 20 4e 45 45 44 42 49 | */. | NEEDBI|
|00005840| 54 53 28 28 75 6e 73 69 | 67 6e 65 64 29 62 64 29 |TS((unsi|gned)bd)|
|00005850| 0d 20 20 20 20 20 20 69 | 66 20 28 28 65 20 3d 20 |. i|f ((e = |
|00005860| 28 74 20 3d 20 74 64 20 | 2b 20 28 28 75 6e 73 69 |(t = td |+ ((unsi|
|00005870| 67 6e 65 64 29 62 20 26 | 20 6d 64 29 29 2d 3e 65 |gned)b &| md))->e|
|00005880| 29 20 3e 20 31 36 29 0d | 20 20 20 20 20 20 20 20 |) > 16).| |
|00005890| 64 6f 20 7b 0d 20 20 20 | 20 20 20 20 20 20 20 69 |do {. | i|
|000058a0| 66 20 28 65 20 3d 3d 20 | 39 39 29 0d 20 20 20 20 |f (e == |99). |
|000058b0| 20 20 20 20 20 20 20 20 | 72 65 74 75 72 6e 20 31 | |return 1|
|000058c0| 3b 0d 20 20 20 20 20 20 | 20 20 20 20 44 55 4d 50 |;. | DUMP|
|000058d0| 42 49 54 53 28 74 2d 3e | 62 29 0d 20 20 20 20 20 |BITS(t->|b). |
|000058e0| 20 20 20 20 20 65 20 2d | 3d 20 31 36 3b 0d 20 20 | e -|= 16;. |
|000058f0| 20 20 20 20 20 20 20 20 | 4e 45 45 44 42 49 54 53 | |NEEDBITS|
|00005900| 28 65 29 0d 20 20 20 20 | 20 20 20 20 7d 20 77 68 |(e). | } wh|
|00005910| 69 6c 65 20 28 28 65 20 | 3d 20 28 74 20 3d 20 74 |ile ((e |= (t = t|
|00005920| 2d 3e 76 2e 74 20 2b 20 | 28 28 75 6e 73 69 67 6e |->v.t + |((unsign|
|00005930| 65 64 29 62 20 26 20 6d | 61 73 6b 5f 62 69 74 73 |ed)b & m|ask_bits|
|00005940| 5b 65 5d 29 29 2d 3e 65 | 29 20 3e 20 31 36 29 3b |[e]))->e|) > 16);|
|00005950| 0d 20 20 20 20 20 20 44 | 55 4d 50 42 49 54 53 28 |. D|UMPBITS(|
|00005960| 74 2d 3e 62 29 0d 20 20 | 20 20 20 20 4e 45 45 44 |t->b). | NEED|
|00005970| 42 49 54 53 28 65 29 0d | 20 20 20 20 20 20 64 20 |BITS(e).| d |
|00005980| 3d 20 77 20 2d 20 74 2d | 3e 76 2e 6e 20 2d 20 28 |= w - t-|>v.n - (|
|00005990| 28 75 6e 73 69 67 6e 65 | 64 29 62 20 26 20 6d 61 |(unsigne|d)b & ma|
|000059a0| 73 6b 5f 62 69 74 73 5b | 65 5d 29 3b 0d 20 20 20 |sk_bits[|e]);. |
|000059b0| 20 20 20 44 55 4d 50 42 | 49 54 53 28 65 29 0d 20 | DUMPB|ITS(e). |
|000059c0| 20 20 20 20 20 54 72 61 | 63 65 76 76 28 28 73 74 | Tra|cevv((st|
|000059d0| 64 65 72 72 2c 22 5c 5c | 5b 25 64 2c 25 64 5d 22 |derr,"\\|[%d,%d]"|
|000059e0| 2c 20 77 2d 64 2c 20 6e | 29 29 3b 0d 0d 20 20 20 |, w-d, n|));.. |
|000059f0| 20 20 20 2f 2a 20 64 6f | 20 74 68 65 20 63 6f 70 | /* do| the cop|
|00005a00| 79 20 2a 2f 0d 20 20 20 | 20 20 20 64 6f 20 7b 0d |y */. | do {.|
|00005a10| 20 20 20 20 20 20 20 20 | 6e 20 2d 3d 20 28 65 20 | |n -= (e |
|00005a20| 3d 20 28 65 20 3d 20 57 | 53 49 5a 45 20 2d 20 28 |= (e = W|SIZE - (|
|00005a30| 28 64 20 26 3d 20 57 53 | 49 5a 45 2d 31 29 20 3e |(d &= WS|IZE-1) >|
|00005a40| 20 77 20 3f 20 64 20 3a | 20 77 29 29 20 3e 20 6e | w ? d :| w)) > n|
|00005a50| 20 3f 20 6e 20 3a 20 65 | 29 3b 0d 23 69 66 20 21 | ? n : e|);.#if !|
|00005a60| 64 65 66 69 6e 65 64 28 | 4e 4f 4d 45 4d 43 50 59 |defined(|NOMEMCPY|
|00005a70| 29 20 26 26 20 21 64 65 | 66 69 6e 65 64 28 44 45 |) && !de|fined(DE|
|00005a80| 42 55 47 29 0d 20 20 20 | 20 20 20 20 20 69 66 20 |BUG). | if |
|00005a90| 28 77 20 2d 20 64 20 3e | 3d 20 65 29 20 20 20 20 |(w - d >|= e) |
|00005aa0| 20 20 20 20 20 2f 2a 20 | 28 74 68 69 73 20 74 65 | /* |(this te|
|00005ab0| 73 74 20 61 73 73 75 6d | 65 73 20 75 6e 73 69 67 |st assum|es unsig|
|00005ac0| 6e 65 64 20 63 6f 6d 70 | 61 72 69 73 6f 6e 29 20 |ned comp|arison) |
|00005ad0| 2a 2f 0d 20 20 20 20 20 | 20 20 20 7b 0d 20 20 20 |*/. | {. |
|00005ae0| 20 20 20 20 20 20 20 6d | 65 6d 63 70 79 28 73 6c | m|emcpy(sl|
|00005af0| 69 64 65 20 2b 20 77 2c | 20 73 6c 69 64 65 20 2b |ide + w,| slide +|
|00005b00| 20 64 2c 20 65 29 3b 0d | 20 20 20 20 20 20 20 20 | d, e);.| |
|00005b10| 20 20 77 20 2b 3d 20 65 | 3b 0d 20 20 20 20 20 20 | w += e|;. |
|00005b20| 20 20 20 20 64 20 2b 3d | 20 65 3b 0d 20 20 20 20 | d +=| e;. |
|00005b30| 20 20 20 20 7d 0d 20 20 | 20 20 20 20 20 20 65 6c | }. | el|
|00005b40| 73 65 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |se | |
|00005b50| 20 20 20 20 20 20 20 20 | 2f 2a 20 64 6f 20 69 74 | |/* do it|
|00005b60| 20 73 6c 6f 77 20 74 6f | 20 61 76 6f 69 64 20 6d | slow to| avoid m|
|00005b70| 65 6d 63 70 79 28 29 20 | 6f 76 65 72 6c 61 70 20 |emcpy() |overlap |
|00005b80| 2a 2f 0d 23 65 6e 64 69 | 66 20 2f 2a 20 21 4e 4f |*/.#endi|f /* !NO|
|00005b90| 4d 45 4d 43 50 59 20 2a | 2f 0d 20 20 20 20 20 20 |MEMCPY *|/. |
|00005ba0| 20 20 20 20 64 6f 20 7b | 0d 20 20 20 20 20 20 20 | do {|. |
|00005bb0| 20 20 20 20 20 73 6c 69 | 64 65 5b 77 2b 2b 5d 20 | sli|de[w++] |
|00005bc0| 3d 20 73 6c 69 64 65 5b | 64 2b 2b 5d 3b 0d 09 20 |= slide[|d++];.. |
|00005bd0| 20 20 20 54 72 61 63 65 | 76 76 28 28 73 74 64 65 | Trace|vv((stde|
|00005be0| 72 72 2c 20 22 25 63 22 | 2c 20 73 6c 69 64 65 5b |rr, "%c"|, slide[|
|00005bf0| 77 2d 31 5d 29 29 3b 0d | 20 20 20 20 20 20 20 20 |w-1]));.| |
|00005c00| 20 20 7d 20 77 68 69 6c | 65 20 28 2d 2d 65 29 3b | } whil|e (--e);|
|00005c10| 0d 20 20 20 20 20 20 20 | 20 69 66 20 28 77 20 3d |. | if (w =|
|00005c20| 3d 20 57 53 49 5a 45 29 | 0d 20 20 20 20 20 20 20 |= WSIZE)|. |
|00005c30| 20 7b 0d 20 20 20 20 20 | 20 20 20 20 20 66 6c 75 | {. | flu|
|00005c40| 73 68 5f 6f 75 74 70 75 | 74 28 77 29 3b 0d 20 20 |sh_outpu|t(w);. |
|00005c50| 20 20 20 20 20 20 20 20 | 77 20 3d 20 30 3b 0d 20 | |w = 0;. |
|00005c60| 20 20 20 20 20 20 20 7d | 0d 20 20 20 20 20 20 7d | }|. }|
|00005c70| 20 77 68 69 6c 65 20 28 | 6e 29 3b 0d 20 20 20 20 | while (|n);. |
|00005c80| 7d 0d 20 20 7d 0d 0d 0d | 20 20 2f 2a 20 72 65 73 |}. }...| /* res|
|00005c90| 74 6f 72 65 20 74 68 65 | 20 67 6c 6f 62 61 6c 73 |tore the| globals|
|00005ca0| 20 66 72 6f 6d 20 74 68 | 65 20 6c 6f 63 61 6c 73 | from th|e locals|
|00005cb0| 20 2a 2f 0d 20 20 77 70 | 20 3d 20 77 3b 20 20 20 | */. wp| = w; |
|00005cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005cd0| 20 20 20 20 2f 2a 20 72 | 65 73 74 6f 72 65 20 67 | /* r|estore g|
|00005ce0| 6c 6f 62 61 6c 20 77 69 | 6e 64 6f 77 20 70 6f 69 |lobal wi|ndow poi|
|00005cf0| 6e 74 65 72 20 2a 2f 0d | 20 20 62 62 20 3d 20 62 |nter */.| bb = b|
|00005d00| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |; | |
|00005d10| 20 20 20 20 20 20 20 20 | 2f 2a 20 72 65 73 74 6f | |/* resto|
|00005d20| 72 65 20 67 6c 6f 62 61 | 6c 20 62 69 74 20 62 75 |re globa|l bit bu|
|00005d30| 66 66 65 72 20 2a 2f 0d | 20 20 62 6b 20 3d 20 6b |ffer */.| bk = k|
|00005d40| 3b 0d 0d 20 20 2f 2a 20 | 64 6f 6e 65 20 2a 2f 0d |;.. /* |done */.|
|00005d50| 20 20 72 65 74 75 72 6e | 20 30 3b 0d 7d 0d 0d 0d | return| 0;.}...|
|00005d60| 0d 69 6e 74 20 69 6e 66 | 6c 61 74 65 5f 73 74 6f |.int inf|late_sto|
|00005d70| 72 65 64 28 29 0d 2f 2a | 20 22 64 65 63 6f 6d 70 |red()./*| "decomp|
|00005d80| 72 65 73 73 22 20 61 6e | 20 69 6e 66 6c 61 74 65 |ress" an| inflate|
|00005d90| 64 20 74 79 70 65 20 30 | 20 28 73 74 6f 72 65 64 |d type 0| (stored|
|00005da0| 29 20 62 6c 6f 63 6b 2e | 20 2a 2f 0d 7b 0d 20 20 |) block.| */.{. |
|00005db0| 75 6e 73 69 67 6e 65 64 | 20 6e 3b 20 20 20 20 20 |unsigned| n; |
|00005dc0| 20 20 20 20 20 20 2f 2a | 20 6e 75 6d 62 65 72 20 | /*| number |
|00005dd0| 6f 66 20 62 79 74 65 73 | 20 69 6e 20 62 6c 6f 63 |of bytes| in bloc|
|00005de0| 6b 20 2a 2f 0d 20 20 75 | 6e 73 69 67 6e 65 64 20 |k */. u|nsigned |
|00005df0| 77 3b 20 20 20 20 20 20 | 20 20 20 20 20 2f 2a 20 |w; | /* |
|00005e00| 63 75 72 72 65 6e 74 20 | 77 69 6e 64 6f 77 20 70 |current |window p|
|00005e10| 6f 73 69 74 69 6f 6e 20 | 2a 2f 0d 20 20 72 65 67 |osition |*/. reg|
|00005e20| 69 73 74 65 72 20 75 6c | 67 20 62 3b 20 20 20 20 |ister ul|g b; |
|00005e30| 20 20 20 2f 2a 20 62 69 | 74 20 62 75 66 66 65 72 | /* bi|t buffer|
|00005e40| 20 2a 2f 0d 20 20 72 65 | 67 69 73 74 65 72 20 75 | */. re|gister u|
|00005e50| 6e 73 69 67 6e 65 64 20 | 6b 3b 20 20 2f 2a 20 6e |nsigned |k; /* n|
|00005e60| 75 6d 62 65 72 20 6f 66 | 20 62 69 74 73 20 69 6e |umber of| bits in|
|00005e70| 20 62 69 74 20 62 75 66 | 66 65 72 20 2a 2f 0d 0d | bit buf|fer */..|
|00005e80| 0d 20 20 2f 2a 20 6d 61 | 6b 65 20 6c 6f 63 61 6c |. /* ma|ke local|
|00005e90| 20 63 6f 70 69 65 73 20 | 6f 66 20 67 6c 6f 62 61 | copies |of globa|
|00005ea0| 6c 73 20 2a 2f 0d 20 20 | 62 20 3d 20 62 62 3b 20 |ls */. |b = bb; |
|00005eb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005ec0| 20 20 20 20 20 20 2f 2a | 20 69 6e 69 74 69 61 6c | /*| initial|
|00005ed0| 69 7a 65 20 62 69 74 20 | 62 75 66 66 65 72 20 2a |ize bit |buffer *|
|00005ee0| 2f 0d 20 20 6b 20 3d 20 | 62 6b 3b 0d 20 20 77 20 |/. k = |bk;. w |
|00005ef0| 3d 20 77 70 3b 20 20 20 | 20 20 20 20 20 20 20 20 |= wp; | |
|00005f00| 20 20 20 20 20 20 20 20 | 20 20 20 20 2f 2a 20 69 | | /* i|
|00005f10| 6e 69 74 69 61 6c 69 7a | 65 20 77 69 6e 64 6f 77 |nitializ|e window|
|00005f20| 20 70 6f 73 69 74 69 6f | 6e 20 2a 2f 0d 0d 0d 20 | positio|n */... |
|00005f30| 20 2f 2a 20 67 6f 20 74 | 6f 20 62 79 74 65 20 62 | /* go t|o byte b|
|00005f40| 6f 75 6e 64 61 72 79 20 | 2a 2f 0d 20 20 6e 20 3d |oundary |*/. n =|
|00005f50| 20 6b 20 26 20 37 3b 0d | 20 20 44 55 4d 50 42 49 | k & 7;.| DUMPBI|
|00005f60| 54 53 28 6e 29 3b 0d 0d | 0d 20 20 2f 2a 20 67 65 |TS(n);..|. /* ge|
|00005f70| 74 20 74 68 65 20 6c 65 | 6e 67 74 68 20 61 6e 64 |t the le|ngth and|
|00005f80| 20 69 74 73 20 63 6f 6d | 70 6c 65 6d 65 6e 74 20 | its com|plement |
|00005f90| 2a 2f 0d 20 20 4e 45 45 | 44 42 49 54 53 28 31 36 |*/. NEE|DBITS(16|
|00005fa0| 29 0d 20 20 6e 20 3d 20 | 28 28 75 6e 73 69 67 6e |). n = |((unsign|
|00005fb0| 65 64 29 62 20 26 20 30 | 78 66 66 66 66 29 3b 0d |ed)b & 0|xffff);.|
|00005fc0| 20 20 44 55 4d 50 42 49 | 54 53 28 31 36 29 0d 20 | DUMPBI|TS(16). |
|00005fd0| 20 4e 45 45 44 42 49 54 | 53 28 31 36 29 0d 20 20 | NEEDBIT|S(16). |
|00005fe0| 69 66 20 28 6e 20 21 3d | 20 28 75 6e 73 69 67 6e |if (n !=| (unsign|
|00005ff0| 65 64 29 28 28 7e 62 29 | 20 26 20 30 78 66 66 66 |ed)((~b)| & 0xfff|
|00006000| 66 29 29 0d 20 20 20 20 | 72 65 74 75 72 6e 20 31 |f)). |return 1|
|00006010| 3b 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |; | |
|00006020| 20 20 20 20 2f 2a 20 65 | 72 72 6f 72 20 69 6e 20 | /* e|rror in |
|00006030| 63 6f 6d 70 72 65 73 73 | 65 64 20 64 61 74 61 20 |compress|ed data |
|00006040| 2a 2f 0d 20 20 44 55 4d | 50 42 49 54 53 28 31 36 |*/. DUM|PBITS(16|
|00006050| 29 0d 0d 0d 20 20 2f 2a | 20 72 65 61 64 20 61 6e |)... /*| read an|
|00006060| 64 20 6f 75 74 70 75 74 | 20 74 68 65 20 63 6f 6d |d output| the com|
|00006070| 70 72 65 73 73 65 64 20 | 64 61 74 61 20 2a 2f 0d |pressed |data */.|
|00006080| 20 20 77 68 69 6c 65 20 | 28 6e 2d 2d 29 0d 20 20 | while |(n--). |
|00006090| 7b 0d 20 20 20 20 4e 45 | 45 44 42 49 54 53 28 38 |{. NE|EDBITS(8|
|000060a0| 29 0d 20 20 20 20 73 6c | 69 64 65 5b 77 2b 2b 5d |). sl|ide[w++]|
|000060b0| 20 3d 20 28 75 63 68 29 | 62 3b 0d 20 20 20 20 69 | = (uch)|b;. i|
|000060c0| 66 20 28 77 20 3d 3d 20 | 57 53 49 5a 45 29 0d 20 |f (w == |WSIZE). |
|000060d0| 20 20 20 7b 0d 20 20 20 | 20 20 20 66 6c 75 73 68 | {. | flush|
|000060e0| 5f 6f 75 74 70 75 74 28 | 77 29 3b 0d 20 20 20 20 |_output(|w);. |
|000060f0| 20 20 77 20 3d 20 30 3b | 0d 20 20 20 20 7d 0d 20 | w = 0;|. }. |
|00006100| 20 20 20 44 55 4d 50 42 | 49 54 53 28 38 29 0d 20 | DUMPB|ITS(8). |
|00006110| 20 7d 0d 0d 0d 20 20 2f | 2a 20 72 65 73 74 6f 72 | }... /|* restor|
|00006120| 65 20 74 68 65 20 67 6c | 6f 62 61 6c 73 20 66 72 |e the gl|obals fr|
|00006130| 6f 6d 20 74 68 65 20 6c | 6f 63 61 6c 73 20 2a 2f |om the l|ocals */|
|00006140| 0d 20 20 77 70 20 3d 20 | 77 3b 20 20 20 20 20 20 |. wp = |w; |
|00006150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00006160| 20 2f 2a 20 72 65 73 74 | 6f 72 65 20 67 6c 6f 62 | /* rest|ore glob|
|00006170| 61 6c 20 77 69 6e 64 6f | 77 20 70 6f 69 6e 74 65 |al windo|w pointe|
|00006180| 72 20 2a 2f 0d 20 20 62 | 62 20 3d 20 62 3b 20 20 |r */. b|b = b; |
|00006190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000061a0| 20 20 20 20 20 2f 2a 20 | 72 65 73 74 6f 72 65 20 | /* |restore |
|000061b0| 67 6c 6f 62 61 6c 20 62 | 69 74 20 62 75 66 66 65 |global b|it buffe|
|000061c0| 72 20 2a 2f 0d 20 20 62 | 6b 20 3d 20 6b 3b 0d 20 |r */. b|k = k;. |
|000061d0| 20 72 65 74 75 72 6e 20 | 30 3b 0d 7d 0d 0d 0d 0d | return |0;.}....|
|000061e0| 69 6e 74 20 69 6e 66 6c | 61 74 65 5f 66 69 78 65 |int infl|ate_fixe|
|000061f0| 64 28 29 0d 2f 2a 20 64 | 65 63 6f 6d 70 72 65 73 |d()./* d|ecompres|
|00006200| 73 20 61 6e 20 69 6e 66 | 6c 61 74 65 64 20 74 79 |s an inf|lated ty|
|00006210| 70 65 20 31 20 28 66 69 | 78 65 64 20 48 75 66 66 |pe 1 (fi|xed Huff|
|00006220| 6d 61 6e 20 63 6f 64 65 | 73 29 20 62 6c 6f 63 6b |man code|s) block|
|00006230| 2e 20 20 57 65 20 73 68 | 6f 75 6c 64 0d 20 20 20 |. We sh|ould. |
|00006240| 65 69 74 68 65 72 20 72 | 65 70 6c 61 63 65 20 74 |either r|eplace t|
|00006250| 68 69 73 20 77 69 74 68 | 20 61 20 63 75 73 74 6f |his with| a custo|
|00006260| 6d 20 64 65 63 6f 64 65 | 72 2c 20 6f 72 20 61 74 |m decode|r, or at|
|00006270| 20 6c 65 61 73 74 20 70 | 72 65 63 6f 6d 70 75 74 | least p|recomput|
|00006280| 65 20 74 68 65 0d 20 20 | 20 48 75 66 66 6d 61 6e |e the. | Huffman|
|00006290| 20 74 61 62 6c 65 73 2e | 20 2a 2f 0d 7b 0d 20 20 | tables.| */.{. |
|000062a0| 69 6e 74 20 69 3b 20 20 | 20 20 20 20 20 20 20 20 |int i; | |
|000062b0| 20 20 20 20 20 20 2f 2a | 20 74 65 6d 70 6f 72 61 | /*| tempora|
|000062c0| 72 79 20 76 61 72 69 61 | 62 6c 65 20 2a 2f 0d 20 |ry varia|ble */. |
|000062d0| 20 73 74 72 75 63 74 20 | 68 75 66 74 20 2a 74 6c | struct |huft *tl|
|000062e0| 3b 20 20 20 20 20 20 2f | 2a 20 6c 69 74 65 72 61 |; /|* litera|
|000062f0| 6c 2f 6c 65 6e 67 74 68 | 20 63 6f 64 65 20 74 61 |l/length| code ta|
|00006300| 62 6c 65 20 2a 2f 0d 20 | 20 73 74 72 75 63 74 20 |ble */. | struct |
|00006310| 68 75 66 74 20 2a 74 64 | 3b 20 20 20 20 20 20 2f |huft *td|; /|
|00006320| 2a 20 64 69 73 74 61 6e | 63 65 20 63 6f 64 65 20 |* distan|ce code |
|00006330| 74 61 62 6c 65 20 2a 2f | 0d 20 20 69 6e 74 20 62 |table */|. int b|
|00006340| 6c 3b 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |l; | |
|00006350| 20 2f 2a 20 6c 6f 6f 6b | 75 70 20 62 69 74 73 20 | /* look|up bits |
|00006360| 66 6f 72 20 74 6c 20 2a | 2f 0d 20 20 69 6e 74 20 |for tl *|/. int |
|00006370| 62 64 3b 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |bd; | |
|00006380| 20 20 2f 2a 20 6c 6f 6f | 6b 75 70 20 62 69 74 73 | /* loo|kup bits|
|00006390| 20 66 6f 72 20 74 64 20 | 2a 2f 0d 20 20 75 6e 73 | for td |*/. uns|
|000063a0| 69 67 6e 65 64 20 6c 5b | 32 38 38 5d 3b 20 20 20 |igned l[|288]; |
|000063b0| 20 20 20 2f 2a 20 6c 65 | 6e 67 74 68 20 6c 69 73 | /* le|ngth lis|
|000063c0| 74 20 66 6f 72 20 68 75 | 66 74 5f 62 75 69 6c 64 |t for hu|ft_build|
|000063d0| 20 2a 2f 0d 0d 0d 20 20 | 2f 2a 20 73 65 74 20 75 | */... |/* set u|
|000063e0| 70 20 6c 69 74 65 72 61 | 6c 20 74 61 62 6c 65 20 |p litera|l table |
|000063f0| 2a 2f 0d 20 20 66 6f 72 | 20 28 69 20 3d 20 30 3b |*/. for| (i = 0;|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
